[boj] 치킨 배달_15686

from itertools import combinations

N, M = map(int, input().split())

graph = list()
distance_list = list()
result_list = list()
result = list()
min_val = 0
temp_list = list()

for _ in range(N):
    graph.append(list(map(int, input().split())))

# 치킨집 좌표 구하기
chk_list = list()
for i in range(N):
    for j in range(N):
        if graph[i][j] == 2:
            chk_list.append((i, j))

# 치킨집 좌표 M개 조합 구하기
cPositions = list(combinations(chk_list, M))

for cPosition in cPositions:
    result.clear()
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                for c in cPosition:
                    distance = abs(i - c[0]) + abs(j - c[1])
                    distance_list.append(distance)
                min_val = min(distance_list)
                result.append(min_val)
                distance_list.clear()
    temp_list = result.copy()
    result_list.append(temp_list)
    # print(result_list)

sum_list = list()
for result in result_list:
    sum_list.append(sum(result))

answer = min(sum_list)
print(answer)

조합을 이용해야 풀기 쉬운 문제였다.

 

코드를 보면 무려 4중 for 루프(;;)가 사용되었는데, 다른 구현 방법이 따로 생각나지 않았다.

 

처음에는 조합을 생각하지 못하고 나올 수 있는 모든 도시의 치킨거리 경우의 수를 구해 오름차순으로 정렬한 뒤 M개만큼만 파악해 나머지에 해당하는 치킨거리를 도출하는 치킨집들을 폐쇄한다는 식으로 풀려했으나 당연히 풀리지 않았다(스스로 생각해낸 계산법이기 때문에 솔직히 정확한지 솔직히 모르겠고 구현할 피지컬도 딸렸다.)

 

이 문제를 어떻게 풀까 고심하다가, 다른 사람의 풀이를 약간 참고하니 조합(Combination)을 통해 M개 만큼의 치킨집의 경우의 수를 구해 도시의 치킨거리를 구하고 비교하는 식으로 푸는 풀이가 있었다. 정말 무릎을 탁 쳤다.

 

하지만 약간의 힌트를 얻었다 해도 역시 피지컬이 딸려 코드를 적어내는데에 어려움이 많았다ㅠㅠ M개만큼의 치킨집의 각각의 경우의 수에서 치킨집의 좌표를 이용해 처리했는데, 4중 for 루프를 코딩하려니 너무 했갈렸다.

 

코딩은 역시 연습만이 답인 것 같다.