[Python] 백준 15686번: 치킨 배달

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

15686번: 치킨 배달

 

import sys
import itertools

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def getMinChickenDistance():
    minChickenDistance = float('inf')

    # 치킨집 위치 & 치킨집 -> 집까지 거리 저장
    chickenPositions = []

    for i in range(N):
        for j in range(N):
            if city[i][j] == 2:
                chickenPositions.append((i, j))
                setDistanceChickenToHouse((i, j))

    # 살아남을 지점들 선택
    cases = list(itertools.combinations(
        chickenPositions, M))

    for chickens in cases:
        curMinDist = {}

        # 각 치킨집 -> house
        for pos in chickens:
            for p, d in distanceChickedToHouse[pos].items():
                if curMinDist.get(p):
                    curMinDist[p] = min(curMinDist[p], d)
                else:
                    curMinDist[p] = d

        minChickenDistance = min(minChickenDistance, sum(curMinDist.values()))

    return minChickenDistance


def setDistanceChickenToHouse(startPos):
    curDist = 0
    isVisited = [[False]*N for _ in range(N)]
    isVisited[startPos[0]][startPos[1]] = True
    todo = [startPos]

    while todo:
        curDist += 1
        nextTodo = []

        for x, y in todo:
            for i in range(4):
                nextX, nextY = x + dx[i], y + dy[i]

                if nextX < 0 or nextX > N-1 or nextY < 0 or nextY > N-1:
                    continue

                if isVisited[nextX][nextY] == False:
                    if city[nextX][nextY] == 1:
                        if distanceChickedToHouse.get(startPos):
                            distanceChickedToHouse[startPos][(
                                nextX, nextY)] = curDist
                        else:
                            distanceChickedToHouse[startPos] = {
                                (nextX, nextY): curDist}

                    isVisited[nextX][nextY] = True
                    nextTodo.append((nextX, nextY))

        todo = nextTodo


if __name__ == '__main__':
    N, M = map(int, input().split())
    city = [list(map(int, input().split())) for _ in range(N)]

    distanceChickedToHouse = {}

    print(getMinChickenDistance())

 

먼저, 치킨집에서 집까지의 거리를 저장(distanceChickenToHouse)한다. 이 때, BFS가 사용되며,  distanceChickedToHouse[(srcX, srcY)][(destX, destY)] = 2와 같은 식으로 저장된다.

다음으로, 치킨집을 M개 선택한 경우의 수(cases)를 저장하고, 여기에 대해서 반복문을 돌아준다. 선택받은 치킨집들에 대해서 또 반복문을 돌아주는데, 현재 치킨집 -> 집까지의 거리를 참조하면서, 각각의 집의 치킨 거리를 갱신해준다. 이렇게 하면 현재 선택받은 치킨집들에 대한 도시 치킨 거리가 나오게 되고, 이 값을 토대로 minChickenDistance에 알맞은 값을 넣어주면 된다.

 

여담이지만, 이 문제는 골드4~3 정도의 난이도라고 생각한다.