백준 15686 치킨 배달 - 골드5 [파이썬]

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

15686번: 치킨 배달

 

구현 카테고리로 검색했는데

이건 그냥 완전탐색 문제 아닌가?

일단은 풀었다.

 

치킨집이 최대 M개까지 있을 수 있다고 했으니까,

1부터 M까지 치킨집의 위치를 조합(combination)으로 내놓은다음

거기에다 모든 집의 위치와 일일히 치킨거리를 구하고

도시의 치킨거리를 최솟값으로 갱신했다.

 

itertools의 combination을 오랜만에 사용해볼 수 있는 문제였다.

 

정답 소스코드

import sys
import itertools
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = []
for i in range(N):
    graph.append(list(map(int, input().split(" "))))
home = []
chicken = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            home.append([i, j])
        if graph[i][j] == 2:
            chicken.append([i, j])

answer = sys.maxsize
# 1부터 탐색
for m in range(1, M+1):
    # 조합 이용 (중복 X)
    for chi in itertools.combinations(chicken, m):
        tmp = 0
        # 모든 집에 대해서 일단 탐색 후, 최솟값으로 갱신
        for h in home:
            chilen = sys.maxsize
            for i in range(m):
                chilen = min(chilen, abs(h[0]-chi[i][0]) + abs(h[1]-chi[i][1]))
            tmp += chilen
        answer = min(answer, tmp)

print(answer)

# 완전탐색, 조합

결과

 

ps.

최근에 삼성SW역량테스트를 보고왔는데,

거기는 아예 외부 라이브러리 사용을 금지했었다.

조합이나 순열같은 알고리즘은 매번 itertools 라이브러리의 힘을 빌리고있는데,

자력으로 풀 수 있도록 공부를 해놓는게 좋을 것 같다.