1. 문제
-
백준 15686과 동일
-
N * N 도시가 빈칸, 치킨집, 집으로 구성되어 있다.
-
도시, (r, c) 행, 열 , 1부터 시작
-
치킨거리 : 집과 가장 가까운 치킨집 사이의 거리
- 도시의 치킨거리는 모든 집의 치킨거리의 합
- 거리는 r1 - r2 , c1 - c2 의 절대값으로 거리를 구한다.
-
지도 표시 방법 : 0 빈칸, 1 집, 2 치킨집
-
목적
- 도시의 치킨거리가 최소가 되도록 치킨집 M개를 남기고 싶다.
-
입력
- N 지도 크기 1 <= N <=50 , M은 치킨집의 수 1<= M <= 13
- 도시 정보
- 집의 개수는 2N개 이하, 적어도 1개 존재
-
출력
- 도시의 치킨 거리의 최소값
입출력 예시
2. 아이디어
- 치킨집 13개 중 M개를 고르는 조합이므로, 10만개 이하의 경우의 수이므로, combinations로 완전탐색해도 시간초과 나지 않을 것이다.
- 지도에서 집과 치킨집의 좌표를 모은다.
- 치킨집을 M개로 구성된 조합의 경우마다, 모든 집까지의 거리를 구하고 그 중 최소값을 구한다.
- 치키집의 조합은 combinations를 이용해서 구한다.
3. 예제코드
# 조합별 최소거리 측정 함수
def cal_distance(candidate):
result = 0
for x1, y1 in house :
temp = 1e9
for x2, y2 in candidate:
temp = min(temp, (abs(x1-x2)+ abs(y1-y2)))
result+=temp
return result
# 입력
n, m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
# 집, 치킨집 좌표 모으기
house = []
chichen = []
for i in range(n):
for j in range(n):
if maps[i][j] == 1:
house.append((i,j))
elif maps[i][j] == 2:
chichen.append((i,j))
# 치킨집 조합 생성
from itertools import combinations
candidates = list(combinations(chichen, m))
# 최적거리
opt = 1e9
for candi in candidates:
opt = min(opt, cal_distance(candi))
print(opt)4. 배운점
- abs, combinations 다시 한번 상기할 수 있었다.
참조
- 이것이 취업을 위한 코딩테스트다. with 파이썬
성장하는 데이터 분석가