[백준 15686] 치킨 배달

문제 보기

이 문제는 브루트 포스 문제이다.

n의 범위가 50이하이고, 선택해야하는 치킨집의 갯수가 13이하이므로, 브루트포스임을 유추할 수 있다.

나는 처음에 문제를 제대로 이해하지 못해서 BFS 문제라고 생각했다. 하지만 모든 경우의 수를 따져봐야 하기때문에, 브루트포스임을 나중에 깨달았다.

문제에서 주어지는 정의는 다음과 같다.

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

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

최대 M개의 치킨집을 고르고, 최솟값이 되는 도시의 치킨거리를 구해야한다.

따라서 주어진 모든 치킨집에서 m개를 선택하는 조합(Combination)을 사용해야한다.

문제를 해결하기 위한 로직은 다음과 같다.

1. 주어진 치킨집에서 M개의 치킨집을 선택할 수 있는 모든 경우의 수를 조사한다. (조합 사용) (18번째 줄)

2. 각 집마다, 해당 조합에 사용되는 치킨집들 중 가장 가까운 치킨거리를 구하고, 이를 도시의 치킨거리에 더해준다. (19~25번째 줄)

3. 계산한 도시의 치킨거리가 최솟값인지 비교하고, 만약 그렇다면 결과값을 업데이트해준다. (26번째 줄)

처음으로 itertools 모듈의 combinations 함수를 써보았다.

코드가 매우 짧아지고 간결해졌다.. 정말 유용한 모듈인 것 같다.

잘 활용할 수 있도록 노력해야겠다.

import sys
from itertools import combinations
 
n, m = map(int, sys.stdin.readline().split())
board = [[0 for c in range(n + 1)] for r in range(n + 1)]
house_list = list()
chicken_list = list()
for i in range(1, n + 1, 1):
    line = sys.stdin.readline().split()
    for j in range(1, n + 1, 1):
        board[i][j] = int(line[j - 1])
        if board[i][j] == 1:
            house_list.append((i, j))
        elif board[i][j] == 2:
            chicken_list.append((i, j))
 
answer = sys.maxsize
for comb in combinations(chicken_list, m):
    city_dist = 0
    for (house_r, house_c) in house_list:
        chicken_dist = sys.maxsize
        for chicken_r, chicken_c in comb:
            dist = abs(chicken_r - house_r) + abs(chicken_c - house_c)
            chicken_dist = min(chicken_dist, dist)
        city_dist += chicken_dist
    answer = min(answer, city_dist)
print(answer)