구현

이것이 코딩테스트다-332p

도시의 크기 N x N , 치킨집 수  M

 

0 : 빈칸

1 : 집

2 : 치킨집

 

치킨 거리: 집과 가장 가까운 치킨집 사이의 거리

도시의 치킨 거리: 모든 집의 치킨 거리

 

=> 목표: 기존에 존재하는 치킨집을 줄여서 최대 M개로 맞추기, 집들로부터 M개의 치킨집까지의 거리 줄이기

 

입력 -> N M

출력 -> 도시의 치킨 거리의 최솟값

 

거리를 구하는 방법

임의의 두 칸 ( r1, c1 ) 과 ( r2, c2) 사이의 거리는 | r1 - r2 | + | c1- c2 |

 

from itertools import combinations   // 조합 라이브러리 사용

n,m = map(int,input().split())  //도시의 크기, 치킨집의 수 받아오기
chicken, house = [], [] 

for r in range(n):  // 도시의 크기 받아온 만큼 for문 
	data = list(map(int,input().split()))
	for c in range(n):
		if data[c]==1: // 1이면 집
			house.append((r,c))
		elif data[c]==2:  // 2면 치킨집
			chicken.append((r,c))

candidates= list(combinations(chicken,m)) // 모든 치킨집 중 m개의 치킨집을 뽑는 조합 계산

def get_sum(candidate): // 치킨 거리의 합 계산
	result=0
	for hx, hy in house: // 모든 집에 대해서 
		temp=1e9 //1e9= 10의 9승
		for cx, cy in candidate:
			temp=min(temp, abs(hx-cx) + abs(hy-cy)) // 가장 가까운 치킨집까지의 거리 구하기
		result += temp
	return result

result=1e9
for candidate in candidates: 
	result=min(result, get_sum(candidate)) // 치킨 거리의 합의 최소를 찾아 출력

print(result)

 

https://blog.naver.com/dbtodus1/222515814482

[Python] 코딩 테스트를 위한 파이썬 문법 정리1 - 자료형

* 1e9와 같은 자료형 문법 참고 블로그

 

 

 

이것이 코딩테스트다 - 325p

자물쇠: 격자 한 칸의 크기가 1 x 1 인 N x N 크기의 정사각 격자 형태

열쇠: M x M 크기의 정사각 격자 형태

 

열쇠-> 회전과 이동 가능

 

열쇠의 돌기 부분을 자물쇠의 홈 부분에 맞게 채우면 자물쇠가 열림

열쇠의 돌기와 자물쇠의 돌기가 만나면 안 됨

 

=> 목표: 열쇠를 적당히 회전하고 이동시켜 자물쇠의 홈에 딱 맞게 끼워 넣는 것

 

 

*이 문제는 프로그래머스 사이트에서 테스트해야 정상 동작한다

https://programmers.co.kr/learn/courses/30/lessons/60059?language=python 

코딩테스트 연습 - 자물쇠와 열쇠

 

 

연산이 많이 필요 -> 완전 탐색을 이용하여 열쇠를 이동이나 회전시켜서 자물쇠에 끼워보는 작업 전부 시도 가능

-> 완전 탐색을 수월하게 하기 위해서 자물쇠 리스트의 크기를 3배 이상으로 변경 -> 자물쇠 리스트에 열쇠 리스트의 값을 더한 뒤에 더한 결과가 자물쇠 부분의 모든 값이 1이면 통과

 

*효율적인 문제 풀이를 위해 rotate_a_matrix_by_90_degree() 함수 구현

= 2차원 리스트를 90도 회전한 결과를 반환하는 함수

 

def rotate_a_matrix_by_90_degree(a):
    n= len(a)
    m=len(a[0])
    result = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j]
    return result

def check(new_lock):
    lock_length = len(new_lock)
    for i in range(lock_length, lock_length *2 ):
        for j in range(lock_length, lock_length *2 ):
              if new_lock[i][j] !=1:
                     return False
    return True

def solution(key, lock):
    n=len(lock)
    m=len(key)
    new_lock = [[0]*(n*3) for _ in range(n*3)]
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n]=lock[i][j]
            
    for rotation in range(4):
        key=rotate_a_matrix_by_90_degree(key)
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] += key[i][j]
                if check(new_lock)==True:
                    return True
                for i in range(m):
                    for j in range (m):
                        new_lock[x+i][y+j]-= key[i][j]

    return False

 

for _ in range 참고 블로그

 

https://syujisu.tistory.com/130

python " _ " (언더바) 쓰임