외판원 순회
코드
n = int(input())
inf = float('inf')
data = [list(map(int, input().split())) for _ in range(n)]
dp = [[inf for _ in range(1 << n)] for _ in range(n)]
def dfs(x, visited): # x : 현재 방문한 노드, visited : 지금까지 방문 노드를 담고있는 기록
if dp[x][visited] != inf: # 겪은 상황일 경우
return dp[x][visited]
if visited == (1 << n) - 1: # 모든 노드를 방문한 경우
if data[x][first] != 0: # 다시 최초 출발지로 돌아가야 한다. x -> first
return data[x][first]
else:
return inf
min_val = inf
for to in range(n): # 전체 노드 방문
if to == first: # 최초 출발지는 제외
continue
if data[x][to] == 0: # x->to의 길이 없는 경우 제외
continue
if visited & (1 << to) != 0: # 방문기록에 존재하는 지점(to)은 제외
continue
min_val = min(min_val, data[x][to] + dfs2(to, visited | (1 << to)))
dp[x][visited] = min_val
return min_val
first = 2 # 최초 출발지 0 ~ n-1 중 임의의 노드를 선택 (무엇을 선택해도 결과는 같다)
print(dfs(first, 2 ** first))접근방식
- dfs -> 전체 경로 탐색
- dp -> 메모이제이션 (이유 : 시간복잡도)
- bitmasking -> dp와 함께 사용 (이유 : 공간복잡도)
dp[0][0111]의 의미
- 현재 방문한 노드는
0이다 - 현재 상태에서 방문기록은
0111이다. (0111은 2진수이다. 10진수로 표현하면 7이다)
0111
^3번 노드의 방문 여부를 나타낸다. (0이므로 아직 방문하지 않은 상태)
0111
^2번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)
0111
^1번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)
0111
^0번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)dp[0][0111] (== dp[0][7])는
⇨ 현재 방문 노드가 0이고 방문기록이 0111(7)일 때 모든 경우에 대해 가장 적은 비용을 담고 있다.
일단 현재 방문 노드가 0이고 방문기록이 0111이라는 건
이전에 방문했던 노드들이 1,2라는 의미다.
이 상황에서 가능한 경로는 1->2->0 또는 2->1->0 경우가 있다.
위와 같은 가능한 경로들 중 비용이 가장 적게 나오는 경로가 dp[0][0111]에 메모된다.
dp[0][0111]가 메모되는 과정
...
def dfs(x, visited):
# 현재 방문한 노드는 x, 현재까지 방문기록은 visited이다.
...
min_val = inf
for to in range(n): # 전체 노드 방문
...
# for 문에서 방문이 가능한 노드들을 고른다.
# "x(현재노드) -> to(그 다음 방문노드) -> ... -> 최초 방문 노드"
# 의 비용을 나타내는 코드가
# data[x][to] + dfs2(to, visited | (1 << to) 이 부분이다.
min_val = min(min_val, data[x][to] + dfs2(to, visited | (1 << to)))
# 현재 방문한 노드는 x, 현재까지의 방문 기록이 visited인 상황에서
# 위 for문을 통해 가능한 모든 경로를 계산하여 그 중 최소 비용이 min_val 변수에 담겨있다.
# 이를 dp[x][visited]에 메모한다.
dp[x][visited] = min_val
return min_val
...
dp[x][visited]에는 가능한 모든 경로를 계산한 뒤 가장 최소 비용이 담겨져 있다는게 포인트이다.
비트마스크를 이용한 집합연산
