[백준] 2098번: 외판원 순회 문제 풀이 파이썬

현톨·2022년 11월 9일
0

문제 링크
백준 2098번: 외판원 순회

전체 코드

import sys
import math

input = sys.stdin.readline
N = int(input())
W = [0] * N
for i in range(N):
    W[i] = list(map(int, input().split()))
M = [[0] * (1 << N) for i in range(N)]

def dfs(node, visited):
    # 모든 도시를 방문 했다면
    if visited == (1 << N) - 1:
        return W[node][0] if W[node][0] else math.inf
    # 최소 비용이 이미 계산 되어있다면
    if M[node][visited] != 0:
        return M[node][visited]
    cost = math.inf
    for i in range(1, N):
        # 해당 도시로 가는 경로가 없다면 skip
        if not W[node][i] or visited & (1 << i):
            continue

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

print(dfs(0, 1))

작성중 ...

profile
기록하는 습관 들이기

0개의 댓글