[백준] 10971번 외판원 문제 2 (by Python)

문제

문제의 구성이 기본적인 측면이 있어 사전지식 없이 아이디어를 떠올려 풀 수 있었으나 더 나은 해법을 찾던 중 해당 문제가 TSP(Traveling Salesperson Problem)라는 유명한 문제라는 것을 알았고, 관련된 알고리즘을 체계적으로 공부해보는 계기가 되었다. 덕분에 비트 연산 및 Dynamic Programming 방법에 대해 생각해볼 수 있어서 좋았다.

 

풀이

def isIn(i, A):
    return (A & (1 << (i - 1))) != 0

def diff(A, j):
    t = 1 << (j - 1)
    return A & (~t)

def minimum(w, D, i, A):
    min_val = INF
    for j in range(1, n):
        if isIn(j, A):
            m = w[i][j] + D[j][diff(A, j)]
            min_val = min(min_val, m)
    return min_val

def travel(n, w):
    size = 2 ** (n - 1)
    D = [[0] * size for _ in range(n)]
    for i in range(1, n):
        D[i][0] = w[i][0]
    for k in range(1, n - 1):
        for A in range(1, size - 1):
            if bin(A).count('1') == k:
                for i in range(1, n):
                    if not isIn(i, A):
                        D[i][A] = minimum(w, D, i, A)
    A = size - 1
    return minimum(w, D, 0, A)

INF = int(1e9)
n = int(input())
w = []
for _ in range(n):
    w.append([INF if m == 0 else m for m in list(map(int, input().split()))])

print(travel(n, w))

참고

위 풀이를 위해 참고한 영상이다. TSP에 대해 더 궁금하시다면 한 번 보는 걸 권한다.

www.youtube.com/watch?v=wj44Dd0zdzM&list=PLHqxB9kMLLaPOp0jh591QhPvbz4H266SS&index=27&ab_channel=%EC%A3%BC%EB%8B%88%EC%98%A8TV%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98%EC%97%B0%EA%B5%AC%EC%86%8C