[Python] 백준 2098번: 외판원 순회

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

2098번: 외판원 순회

 

import sys
input = sys.stdin.readline


def getMinCost(index, isVisited):
    # Base Case
    # 모든 곳을 방문했을 경우
    if isVisited == MAX_BINARY:
        if W[index][START_INDEX] != 0:
            return W[index][START_INDEX]
        else:
            return INF

    # 이미 같은 방법으로 방문한 적이 있을 경우
    if dp[index][isVisited] != 0:
        return dp[index][isVisited]

    # Recursive Case
    # 아직 방문하지 않은, 방문 가능한 도시들을 돌면서 minCost 갱신
    minCost = INF
    for i in range(N):
        if getBitFromBinary(isVisited, i) == 0 and W[index][i] != 0:
            minCost = min(
                minCost, W[index][i] + getMinCost(i, setBinaryTrue(isVisited, i)))

    dp[index][isVisited] = minCost

    return minCost


def setBinaryTrue(binary, index):
    return binary | 1 << index


def getBitFromBinary(binary, index):
    return (binary >> index) % 2


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

    START_INDEX = 0
    MAX_BINARY = (1 << N) - 1
    INF = 1000001*16

    dp = [[0]*(MAX_BINARY + 1) for _ in range(N)]

    minCost = getMinCost(START_INDEX, 1)
    print(minCost)

 

이 문제는 DFS, DP, 그리고 Bitmask가 동시에 쓰이는 문제이다.

 

우선 전체적인 틀은 DFS이다. getMinCost(index, isVisited)는 index부터 시작해서 START_INDEX(0으로 정하였는데, 탐색 시작점이 어떤 도시이든 모두 같은 값을 얻게 된다.)까지 외판원 순회를 마쳤을 때의 최소 비용을 가져오는 DFS 함수이다.

여기서 isVisited는 말그대로 각각의 도시에 방문하였는지 여부를 체킹하는 용도로 쓰인다. 다만 True/False로 구분되는 리스트가 아니라, 비트마스킹을 이용한다는 점이 중요하다. 기본적으로 공간복잡도가 매우 줄어드는데, 이런 특성을 통해서 이후에 설명할 DP의 정보 저장에도 쓰일 수 있다.

 

 

내 코드에서 쓰인 비트마스킹에 대한 함수는 setBinaryTrue()와 getBitFromBinary()가 있다.

우선 setBinaryTrue는 index번째의 bit를 1로 바꿔야하는데, 이것을 or 연산을 통해 쉽게 해준다. 가령, binary가 1001이고, index가 2라면, 1001 | 100이라는 연산을 수행하여 최종적으로 1101을 만들어낸다.

다음으로 getBitFromBinary()인데, 이 함수는 index번째의 bit를 반환해주는 역할을 수행한다. 이것을 위해, index번째의 bit가 첫번째 자리로 오게끔 >> 연산을 index만큼 수행해주고, 이것을 2로 나눈 나머지를 반환해주면 된다. 가령 binary가 1101이고, index가 2일 때, 1101 >> 2를 수행하여, 11을 만들어주고 이것을 2로 나눈 나머지, 즉 1을 반환해준다.

 

 

아무튼, isVisited를 비트마스킹을 통해 갱신해가면서 DFS를 돌리게 되는데, 여기서 Base Case는 다음과 같다.

if isVisited == MAX_BINARY:

여기서 MAX_BINARY는 초기에 (1 << N) - 1으로 정의를 해두었는데, 이것은 모든 도시를 방문했을 때의 바이너리이다. 즉, N이 4일 때 MAX_BINARY는 1111이 된다는 것이다. 따라서, 해당 조건이 참이라는 것은, 탐색을 계속하다가, 결국에 모든 도시에 방문하게 되었다는 것이다. getMinCost()라는 함수가, index에서 START_INDEX까지 방문할 때의 최소값을 반환하는 함수이므로, 바로 W[index][START_INDEX]를 반환해주면 된다. 다만, W[index][START_INDEX]가 0(즉, 방문할 수 없는 경우)일 때에는 INF를 반환해준다.

 

 

다음으로, dp에 대한 if문은 우선 제쳐두고, Recursive Case에 대한 설명이다. 이부분은 크게 어려울 것 없는데, 0~N-1까지 돌면서, 해당하는 도시가, 아직 방문하지 않았으며(getBitFromBinary()로 얻은 값이 0이어야함), 방문 가능(W[index][i]가 0이 아니어야함)할 경우, 해당 도시에 대한 탐색을 하여, minCost를 갱신시켜준다. 여기서, 아래 코드에 대한 의미를 짚고 넘어가자.

W[index][i] + getMinCost(i, setBinaryTrue(isVisited, i))

W[index][i]는 말그대로 index->i의 비용을 의미하며, + 기호 이후의 것은, getMinCost()의 의미를 잘 생각해보면 알겠지만, i->START_INDEX의 최소 비용을 의미한다. 즉 이 둘을 합치게 되면 index->START_INDEX의 최소 비용이 된다. 이렇게 되면 getMinCost()에서 마지막으로 리턴하게 될 minCost가, 이 함수의 설계대로 올바른 값을 갖게 된다.

그리고, getMinCost()의 파라메터에 setBinaryTrue()가 있는데, 이를 통해 현재의 isVisited라는 정보에서, 다음으로 방문할 도시(i)에 방문했다라는 정보가 추가된 새 binary를 다음 재귀 함수에 전달하게 된다.

 

 

이렇게만 해도, 문제에서 원하는 값을 모두 얻어낼 수 있다. 하지만 처음에 언급한 바와 같이, dp를 써야하는데, dp를 쓰지 않으면 시간초과로 이 문제를 풀 수 없기 때문이다. 우선 dp[i][binary]는, i->START_INDEX를 방문하기 위한 최소비용인데, 이 정보는 binary라는 방문 정보(isVisited의 형식과 같음)들을 통해 구분된다. 예를 들어, 탐색을 0->1->2->3->0으로 할 것이라고 해보자. 또한 탐색을 하면서, getMinCost(2, 0b11)를 호출하였고, 탐색 결과 2->3->0에서의 비용이 17이 나왔다고 가정하자. 해당 함수 내에서, dp[2][0b111] = 17이라는 대입이 발생한다.

이런 식으로 dp가 갱신이 되는 것이고, 이 dp는 getMinCost()의 중반부에서 조건문을 통해 시간복잡도를 훌륭하게 해준다. 주석에 설명한 바와 같이, 이미 같은 방법(방문 정보가 같음)으로 index에 대해서 함수를 호출한 적이 있을 경우(dp는 처음에 0으로 초기화되는 것을 명심하자.)에는, for문에 의한 탐색을 진행하지 않고, 미리 저장되어있는 dp를 곧바로 리턴해주는 것이다.