백준[ 15686 | Python ] 치킨 배달

문제

https://www.acmicpc.net/problem/15686

풀이

가장 먼저 주어지는 것은 거리의 크기인 N, 최대로 남길 치킨 집의 갯수 M이다. 이 다음 줄 부터 N번째 줄 까지 거리가 나타나는데 이 때 0은 빈칸, 1은 집, 2는 치킨 집이다. 이 안에서 최대 M개의 치킨집을 골랐을 때 집과 치킨집의 거리의 합인 치킨 거리의 최소값을 구하는 문제이다.

중요한 점은 치킨 거리를 집과 치킨집의 차에 절대값을 취하여 구하기 때문에 전체적인 거리의 모습을 저장하기보다는 치킨집과 집의 인덱스를 저장해야 한다는 것이다.

또한 치킨집을 최대 M개를 골라야 하기 때문에 x개 중 y개를 뽑는 경우의 수를 고려하기 위해서 조합을 이용해야 한다. 이는 파이썬의 라이브러리인 itertools의 combinations를 이용해 쉽게 구현할 수 있다.

정리해서 말하자면, 치킨집과 집의 인덱스를 저장하여 조합을 통해 치킨집을 최대 M개 뽑은 경우에서 모든 집과의 최소거리를 구한 뒤 모두 더해 해결할 수 있다.

import sys
from itertools import combinations

input = sys.stdin.readline

N,M = map(int, input().split())
home_idx = []
chicken_idx = []

for i in range(N):
    s = list(map(int,input().split()))
    for j in range(N):
        if s[j] == 1:
            home_idx.append((i,j))
        elif s[j] == 2:
            chicken_idx.append((i,j))

min_d = 10**30

for c in combinations(chicken_idx,M):
    total_d = 0
    for h in home_idx:
        total_d += min([abs(h[0]-i[0])+abs(h[1]-i[1]) for i in c])
        if min_d <= total_d:
            break
    min_d = min(total_d,min_d)
    
print(min_d)

생각 & 정리

최대 M개를 고르는 조건 때문에 해맸다.
또한 처음 주어지는 두 수를 r,c로 착각했기 때문에 시간이 많이 걸렸다.
손코딩을 먼저하고 하는 습관을 기르려다가 구현문제라고 직접 코드로 옮겼는데, 역시 문제를 꼼꼼히 읽고 손으로 미리 작성해두는 습관을 버리면 안될 것 같다.