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

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

2098번: 외판원 순회

처음 해당 문제를 접했을때 완전탐색 + 백트래킹 문제로 보고 문제를 풀어보려고 하였습니다. 팩토리얼 시간복잡도를 가지게 되고, 원하는 시간에 문제를 해결 할 수 없습니다.

 

해당 문제를 풀면서 이틀 동안 머리가 너무 지끈 했습니다... ㅠ 오랜 시간 분석 끝에 이해하게 되었습니다. 다이나믹 프로그래밍과 비트마스킹으로 문제로 해결 할 수 있습니다.

 

dp 테이블을 dp[i][visited]로 둘 수 있는데, i는 i노드에서 visited에 비트연산된 노드를 제외한 나머지 노드를 방문 한 최소거리 입니다.

예를들어 노드가 5개가 있다고하면, dp[3][00111]을 분석해보겠습니다. visited는 실제로 정수이고 예제를 보기 편하게 위하여 비트로 표현하였습니다. 00111 은 { 1번,2번,3번 } 을 방문한 상태이고 앞으로 4번 노드와 5번노드 1번노드(자기자신)을 방문할 최소거리 값 입니다.

정리하자면 3번노드 -> 4번노드 -> 5번노드 -> 1번노드 (자기자신) 를 방문한 최소거리 값 입니다.

dp 테이블을 다음과 같이 잡은 이유를 예를 들어 보겠습니다.

1번 -> 2번 -> 3번 -> 4번-> 5번 -> 1번 으로 가는경우와 1번 -> 3번 -> 2번 -> 4번-> 5번 -> 1번 으로 가는 경우가 있다고 한다면

4번 -> 5번 -> 1번 노드를 방문하는 값이 중복됩니다.

즉 dp[5][1번2번3번4번]가 중독되서 연산이 됩니다.

 

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

INF = int(1e9)
dp = [[None] * (1 << N) for _ in range(N)] # N을 좌 shfit 하면 N*2 가 된다.
def dfs(i, visited):
    if visited == (1 << N) -1: # 모든 도시를 다 방문 했다면 (비트 의 전체합 -1 이면 모두 방문한 상황)
        if graph[i][0]:
            return graph[i][0] # 출발점으로 가는 경로가 있다면 출발점으로 가는 경로 출력
        else:
            return INF # 출발점으로 가는 경로가 없다면 INF 출력
        
    if dp[i][visited] != None: # 이미 최소비용이 계산되어있다면 출력
        return dp[i][visited]
    
    temp = INF
    for x in range(1, N):
        if not graph[i][x] or visited & (1 << x): # 가는 경로가 없거나 이미 방문한 도시라면 skip
            continue
        
        temp = min(temp, dfs(x, visited | (1 << x)) + graph[i][x]) # i가 4일경우 10000 값을 or 연산한다.
        
    dp[i][visited] = temp
    return temp
            
print(dfs(0,1))