백준 2098 외판원 순회(python)

문제

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

2098번: 외판원 순회

---

외판원 순회 2 문제와 다르게 시간과 메모리 조건이 달랐기 때문에 비트 마스크 개념과 dp개념을 사용하여 접근한 문제입니다. 순회하면서 방문하는 노드의 상태를 비트의 형태로 표현해 주었습니다.  과정은 다음과 같습니다.

• 순회하면서 메모이제이션할 값들을 현재의 노드와 상태를 기준으로 저장해 주었습니다.
• 순회하면서 기존에 저장한 값이라면 dp 리스트에 저장된 값을 바로 리턴해 주었습니다.
• 현재 노드에서 갈 수 있는 노드들을 찾아서 비트에 표시해 주고 다음 상태로 전달했습니다.
• 최적 부분 구조를 유지하기 위해서 현 상태에서 시작하는 부분 경로의 최솟값을 리턴하였습니다.

---

소스코드 

import sys


def go(now, trace):
    if dp[now][trace]:
        return dp[now][trace]

    # 기저 조건
    if trace == (1 << N)-1:
        return path[now][0] if path[now][0] > 0 else MAX

    # 각 상태에서 구해야하는 값
    cost = MAX
    for i in range(1, N):
        if not trace & (1 << i) and path[now][i]:
            val = go(i, trace | (1 << i))
            cost = min(cost, val+path[now][i])

    # dp에 값 갱신
    dp[now][trace] = cost
    return dp[now][trace]


N = int(input())
path = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (1 << N) for _ in range(N)]
MAX = sys.maxsize

# print(dp)
print(go(0, 1))