2098_외판원순회 1

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

2098번: 외판원 순회

 

 

해당문제를 풀기 위해선 비트마스크, dp , dfs 총 3가지의 알고리즘을 활용해서 풀 수 있다.

 

처음에 비트마스크와 dp만 가지고 풀어보려다가 많이 헤맸던 문제이다..

 

먼저 dp는 2차원 dp로 선언을 한 후

 

dp[i][j]라면 i는 현재 도시의 위치, j는 현재까지 방문한 도시들을 기록한다.

 

이때 j를 비트마스크를 이용해서 기록한다. 

 

즉, 현재 도시가 3이고 방문을 1,2번째 도시인 11을 방문했다면

 

dp[3][3] 이 되는 것이다.

 

 

dfs를 만들어서 전체를 탐색하는데 인자로는 현재 도시와 visited를 가져온다.

만약 visited가 다 채워지면 출발지로 향하는 값을 반환한다. 이경우, 시작지는 0으로 두었는데 그 이유는 어차피 순회이기 때문에 시작지를 어디로 잡아도 상관없기 때문.

 

만약 dp를 한번 방문해서 최소를 방문했다면 굳이 재탐색 하지는 않게한다.

 

이런식으로 dfs를 사용해서 역으로 불러와서 dp를 채우면 시작지의 dp에 전체 최소값이 더해져서 저장되게 된다.

 

n = int(input())

INF = int(1e9)
dp = [[INF] * (1 << n) for _ in range(n)]
W = [ list(map(int,input().split())) for _ in range(n)]
def dfs(node,visited):

    if visited == (1<<n)-1:
        if W[node][0]:
            return W[node][0]
        else:
            return INF

    if dp[node][visited] != INF:
        return dp[node][visited]

    for i in range(1,n):
        if not W[node][i]:
            continue
        if visited & (1<<i):
            continue

        dp[node][visited] = min(dp[node][visited],dfs(i,visited | (1<<i)) + W[node][i])
    return dp[node][visited]

print(dfs(0,1))