[다이나믹 프로그래밍/파이썬] 백준 2098번 : 외판원 순회 / 골드 1

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

2098번: 외판원 순회

n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

dp = [[-1 for _ in range(1 << n)] for _ in range(n)]
inf = 9876543210

def recursion(cur, visited):
    # all node visit
    if visited == (1 << n)-1:
        if board[cur][0] == 0:
            return inf
        dp[cur][visited] = board[cur][0]
        return board[cur][0]

    # memoization
    if dp[cur][visited] != -1:
        return dp[cur][visited]

    min_dist = inf
    for i in range(n):
        # if not visited i-node yet + board not zero
        if not visited & (1 << i) and board[cur][i] != 0:
            min_dist = min(min_dist, board[cur][i] + recursion(i, visited | (1 << i)))

    dp[cur][visited] = min_dist
    return min_dist

print(recursion(0, 1))

외판원 순회 문제는 웰노운 문제고, 재귀를 통해 쉽게 구현을 할 수는 있지만

이 문제에선 완전 탐색만으로는 풀리지 않고 비트마스킹 + dp를 이용해야 한다. (시간 제한이 빡세서..!)

 

1. 재귀 구조의 말단 노드 처리

비트마스킹을 사용하여 모든 노드를 방문했는지 체크하고, 만약 그렇다면 board[cur][0], 즉 현재노드(cur)에서 출발지(0)까지의 거리를 리턴해준다.

 

2. 메모이제이션 사용

처음에 1차원 dp를 설정했다가 답이 계속 틀려서 고민 끝에 수정함.

2차원 dp가 필요한 이유는 visited 정보뿐만 아니라 출발지에 대한 정보를 담고 있어야 하기 때문

즉 dp[node][visited]은 node에서 출발하여 방문하지 않은 곳을 다 돌고 돌아갈 때 최소 거리다.

 

3. 재귀 함수의 핵심 코드

반복문으로 노드를 탐색하며 만약 방문하지 않았고, 방문이 가능할 시 => 재귀 구조 사용으로 탐색을 이어나감