백준 2098번: 외판원 순회 (Python)

접근

이전 문제에서 사용했던 비트마스크를 이용한 dp 문제였다.

2021.05.10 - [코딩/백준 (Python)] - 백준 1311번: 할 일 정하기 1 (Python, PyPy3)

백준 1311번: 할 일 정하기 1 (Python, PyPy3)

이전 문제와 다른 점은 한 도시에서 다른 도시로 가는 길에 가중치가 있다는 것과, 경로가 없을 수 있다는 것, 그리고 처음 지점으로 돌아와야 한다는 것이다.

조금만 생각해보면 처음 지점으로 돌아와야 한다는 것은 즉 순환을 이룬다는 것이므로, 경로가 같으면 어떤 도시에서 출발하더라도 순회 비용은 동일하다. 그러므로 무조건 0 에서 출발하여 순회하면서 가장 작은 순회 비용을 구하면 정답이 된다.

코드

import sys

INF = float('inf')
n = int(sys.stdin.readline())
w = []
for _ in range(n):
    w.append(list(map(int, sys.stdin.readline().split())))
dp = [[-1] * (1 << n) for _ in range(n)]


def dfs(x, visited):
    if visited == (1 << (n - 1)) - 1:  # n - 1 개 도시를 모두 순환했을 때
        if w[x][0]:  # 마지막 도시에서 0으로 돌아갈 경로가 있다면 리턴
            return w[x][0]
        else:  # 없다면 INF 리턴
            return INF
    if dp[x][visited] != -1:
        return dp[x][visited]
    dp[x][visited] = INF
    for i in range(1, n):
        if not w[x][i]:  # x 에서 i 로 가는 경로가 없다면 continue
            continue
        if visited & (1 << i - 1):  # i 에 이미 순회 했다면 continue
            continue
        dp[x][visited] = min(dp[x][visited], dfs(i, visited | (1 << (i - 1))) + w[x][i])
    return dp[x][visited]


print(dfs(0, 0))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!