[BOJ] 치킨 배달(15686) - PYTHON

치킨집과 집의 정보가 담긴 N * N 크기의 2차원 배열이 주어질 때,  M개의 치킨집만 남겼을 때 치킨집 <-> 집 거리 합의 최솟값을 구하는 문제다. N은 최대 50, M은 최대 13이다. 치킨 집의 개수도 13 이하이다.

15686번: 치킨 배달

---

풀이과정

우선 치킨 집 중에서 M개의 치킨집을 골라야 한다. 치킨집과 M의 크기가 최대 13이므로 치킨집을 고르는 경우의 수는 최대 13C6 = 1716가지다.

이렇게 M개의 치킨집을 고른 뒤 각 집의 좌표에서 가장 가까운 치킨집까지의 거리를 구한다. 구하는 방법은 모든 치킨집까지의 거리를 계산한 후 최소값을 얻으면 된다.

이렇게 모든 집에서 치킨집까지의 최소거리를 합한다. 이 과정을 모든 경우의 수를 반복하면서 최소값을 구한다.

---

코드

from itertools import combinations
 
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
chicken = []
house = []
answer = 987654231
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 2:
            chicken.append((i, j))
        elif matrix[i][j] == 1:
            house.append((i, j))
for comb in combinations(chicken, M):
    temp = 0
    for x, y in house:
        cd = 987654321
        for cx, cy in comb:
            cd = min(cd, abs(x - cx) + abs(y - cy))
        temp += cd
    answer = min(answer, temp)
print(answer)

주석 추가

from itertools import combinations
 
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]  # 집, 치킨집 좌표
chicken = []  # 치킨 집 좌표
house = []  # 집 좌표
answer = 987654231
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 2:  # 좌표에서 치킨집이면
            chicken.append((i, j))  # 해당 좌표 치킨집 배열에 추가
        elif matrix[i][j] == 1:  # 좌표에서 집이면
            house.append((i, j))  # 해당 좌표 집 배열에 추가
for comb in combinations(chicken, M):  # 전채 치킨집 중에 M개의 치킨집을 선택해서
    temp = 0  # 현재 경우의 수에서 치킨거리의 합
    for x, y in house:  # 집 좌표를 하나씩 가져와서
        cd = 987654321  # 현재 집의 치킨거리
        for cx, cy in comb:
            cd = min(cd, abs(x - cx) + abs(y - cy))  # M개의 치킨집들 과의 거리 최소값을 구한다
        temp += cd  # 해당 집의 치킨거리를 더한다.
    answer = min(answer, temp)  # 정답 값 = min(현재 경우의 수에서 나온 치킨거리 합, 정답값)
print(answer)

---

채점 결과

처음에는 좌표가 나와서 치킨거리를 찾을 때 BFS로 구하는 코드를 짰는데 시간 초과가 났다. 왜 시간 초과가 나는 줄 모르겠어서 다른 사람들의 풀이를 봤다. 그 결과 좌표 중간에 장애물이 있는 경우가 아니므로 그냥 각 치킨집 좌표에서 집의 좌표를 뺌으로써 구할 수 있다는 것을 알게 됐다. 좌표만 보면 무지성으로 BFS를 짜고 있으면 안 되겠다고 생각했다.

BFS 시간초과 코드

from itertools import combinations
from collections import deque
 
 
def BFS(matrix, house, N):
    rt = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    for sx, sy in house:
        visit = [[-1] * N for _ in range(N)]
        q = deque()
        q.append((sx, sy))
        visit[sx][sy] = 0
        while len(q) > 0:
            x, y = q.popleft()
            if matrix[x][y] == 2:
                rt += visit[x][y]
                break
            for tx, ty in zip(dx, dy):
                nx = x + tx
                ny = y + ty
                if 0 <= nx < N and 0 <= ny < N and visit[nx][ny] == -1:
                    q.append((nx, ny))
                    visit[nx][ny] = visit[x][y] + 1
    return rt
 
 
if __name__ == "__main__":
    N, M = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    chicken = []
    house = []
    answer = 987654231
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 2:
                chicken.append((i, j))
            elif matrix[i][j] == 1:
                house.append((i, j))
    for comb in combinations(chicken, len(chicken) - M):
        for x, y in comb:
            matrix[x][y] = 0
        answer = min(answer, BFS(matrix, house, N))
        for x, y in comb:
            matrix[x][y] = 2
    print(answer)