[백준] 15686번 치킨 배달 (Python)

백준 15686 치킨 배달

입력값의 범위는 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)로 작은 편이라는 것을 알 수 있었다. 또한 집의 갯수는 2N을 넘지 않고 치킨집의 갯수는 13보다 작거나 같기 때문에 모든 경우의 수를 따져 봐도 100 * 13C6(1716)으로 1억을 넘어가지 않는 것을 확인할 수 있다. 일반적으로 경우의 수가 1억 일 때 1초가 걸린다고 계산하면 얼추 맞는다. 이 문제에서는 1초가 주어졌기 때문에 경우의 수가 1억이 넘어가지 않아 완전 탐색을 고려해야 한다. 시간 단축을 위해 DP도 활용했지만 구글링을 해보니 계산이 단순해 DP를 활용하지 않아도 문제를 풀 수 있었다. 문제의 포인트는 이러하다.

1. 그리디 알고리즘으로 해결할 수 없는 문제이므로, 완전 탐색을 해야 한다.
2. 모든 경우의 수를 고려하기 위해 치킨집의 조합을 구한다.
3. 치킨 집의 조합을 활용해 각 조합에서의 치킨 거리를 계산하고 최댓값을 구한다.

다른 분의 정답은 이러하다.

from itertools import combinations 
​
n, m = map(int, input().split())
answer = float('inf')
​
house, chicken = [], []
​
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))
​
for combi in combinations(chicken, m):
  total_distance = 0
  for r1, c1 in house:
    distance = float('inf')
    for r2, c2 in combi:
      distance = min(distance, abs(r1 - r2) + abs(c1 - c2))
      total_distance += distance
      answer = min(answer, total_distance)

print(answer)

내 정답에서는 몇가지 포인트가 있었다.

1. DP에는 각 집에서 몇번 치킨 집이 가까운지, 거리는 얼마나 되는지를 저장한다.
2. BFS를 활용하여 가까운 치킨 집의 인덱스와 거리를 가까운 순으로 저장한다.
3. 치킨 집의 조합마다 DP에 저장된 리스트를 활용하여 가까운 순서대로 해당 치킨 집이 조합에 있는지 확인하고 현재 조합에 있다면 해당 거리를 더한다.

import sys
from itertools import combinations
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
house = []
chicken = []
dp = [[[] for _ in range(n)] for __ in range(n)]
house_mean = [0, 0]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dq = deque()
cnt = 0

for y in range(n):
    for x in range(n):
        if grid[y][x] == 1:
            house.append([y, x])
        elif grid[y][x] == 2:
            chicken.append([y, x])
            dq.append([y, x, cnt, 0])
            dp[y][x].append([cnt, 0])
            cnt += 1

visited = [[[False for _ in range(n)] for __ in range(n)] for ___ in range(len(chicken))]
for i in range(len(chicken)):
    visited[i][chicken[i][0]][chicken[i][1]] = True

while dq:
    y, x, cnt, dist = dq.popleft()
    for i in range(4):
        tmpY = y + dy[i]
        tmpX = x + dx[i]
        if n > tmpY >= 0 and n > tmpX >= 0 and not visited[cnt][tmpY][tmpX]:
            visited[cnt][tmpY][tmpX] = True    
            dp[tmpY][tmpX].append([cnt, dist + 1])
            dq.append([tmpY, tmpX, cnt, dist + 1])

house_mean = [sum(x[0] for x in house) / len(house), sum(x[1] for x in house) / len(house)]
res = 1e9
resPos = []
for comb in combinations(range(len(chicken)), m):
    tmpRes = 0
    for y, x in house:
        for chicken_num, dist in dp[y][x]:
            if chicken_num in comb:
                tmpRes += dist
                break
    res = min(res, tmpRes)

print(res)