[백준알고리즘] 2098번: 외판원 순회 -Python

[백준알고리즘] 2098번: 외판원 순회 -Python

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

2098번: 외판원 순회

전에 외판원 순회 2를 푼 적이 있었는데, 그 이전 문제인 것 같다.

풀이는 여기에 썼었다.

 

외판원 순회 2와 같은 방법으로 문제를 풀면 된다. 전에 비트 마스크로 풀었던 기억이 인상 깊게 남아있었어서, 그렇게 풀까 하다가 브루트 포스 방식으로 풀어봤었는데 안 풀렸다.

 

그래서 결국 예전에 풀었던 비트 마스크 방법으로 풀려고 하는데.. 여기저기서 조금씩 잘못 쓴 것 때문에 한참 틀렸었다...

특히 비용이 0이면 연결이 안 되어있다는 부분 때문에 한참을..

 

자세한 방법과 비트 마스크를 공부할 때 참고한 블로그를 외판원 순회 2에서 열심히 적었었기 때문에 생략하겠다.

def tsp(idx, path):
    if path == total:
        return table[idx][0] if table[idx][0] > 0 else 20202020
    if memo[idx][path] > 0:
        return memo[idx][path]
        
    tmp = 20202020
    for i in range(1, n):
        if (path >> i)%2 == 1 or table[idx][i] == 0: continue
        tmp = min(tmp, table[idx][i] + tsp(i, path|(1<<i)))
    memo[idx][path] = tmp
    return tmp

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]
memo = [[0]*(1<<n) for _ in range(n)]
total = (1<<n)-1
print(tsp(0, 1))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다