228. 외판원 순회 2

백준

1. DFS

import sys
input = sys.stdin.readline

n = int(input())

costs = [[0] * n for _ in range(n)]
for i in range(n):
    costs[i] = list(map(int, input().split()))


def dfs(start, v, visited, value):
    global min_value

    if len(visited) == n:
        if costs[v][start] != 0:
            min_value = min(min_value, value + costs[v][start])
        return

    for i in range(n):
        if i != start and costs[v][i] != 0 and i not in visited:
            visited.append(i)             # 방문 처리를 하고,
            value += costs[v][i]
            dfs(start, i, visited, value)  # 다음 도시로 이동,
            value -= costs[v][i]
            visited.pop()                 # 그 도시의 모든 경우를 확인 하고, pop -> 다음 도시로


min_value = sys.maxsize
for i in range(n):  # start 증가
    dfs(i, i, [i], 0)

print(min_value)

비트 마스킹

참고

import sys
N = int(sys.stdin.readline())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[0] * (1 << N - 1) for _ in range(N)]

def solution(i, route):
    if dp[i][route] != 0:
        return dp[i][route]

    if route == (1 << (N - 1)) - 1:
        if W[i][0]:
            return W[i][0]
        else:
            return float('inf')
            
    min_dist = float('inf')
    for j in range(1, N):
        if not W[i][j]:
            continue
        if route & (1 << j - 1):
            continue
        dist = W[i][j] + solution(j, route | (1 << (j - 1)))
        if min_dist > dist:
            min_dist = dist
    dp[i][route] = min_dist
    
    return min_dist

print(solution(0, 0))