[정글 알고리즘] - [상] -백준 2098번 외판원 순회

 

 

이번 문제는 도시를 한 번씩만 방문하고 다시 출발점으로 돌아오는 최소 비용을 구하는 문제입니다. 겉으로 보면 순열을 전부 확인해야 할 것처럼 보이지만, 도시 수가 최대 16개라서 그런 방식은 불가능합니다. 핵심은 현재 도시와 방문한 도시 집합을 하나의 상태로 묶는 비트마스크 DP입니다.

핵심 요약

• 상태는 dfs(cur, visited) 로 정의합니다.
• 현재 도시와 방문 집합이 같으면, 그 뒤의 최소 비용은 항상 같습니다.
• 모든 도시를 방문하면 출발 도시로 돌아가는 비용만 더하면 됩니다.
• 길이 없는 경우는 비용이 0이므로 다음 상태 후보에서 제외합니다.
• 시간 복잡도는 O(N² · 2^N) 입니다.

1. 문제 설명

백준 2098번 외판원 순회 는 한 도시에서 출발해 모든 도시를 정확히 한 번씩 방문한 뒤 다시 출발 도시로 돌아오는 최소 비용을 구하는 문제입니다.

비용은 행렬 W[i][j] 형태로 주어지고, W[i][j] 와 W[j][i] 는 다를 수 있습니다. 즉 방향성이 있는 비용 그래프라고 보면 됩니다.

입력 범위가 N ≤ 16 이라서 순열 완전탐색은 불가능합니다. 그래서 상태 압축을 이용한 DP가 필요합니다.

2. 왜 이 풀이가 맞는지

이 문제에서 남은 최소 비용을 결정하는 데 필요한 정보는 두 가지뿐입니다. 지금 어느 도시에 있는가, 그리고 어떤 도시를 이미 방문했는가 입니다.

예를 들어 현재 2번 도시에 있고 방문 집합이 0011 이라면, 거기까지 어떤 경로로 왔는지는 중요하지 않습니다. 이후 남은 도시들을 어떻게 돌고 출발점으로 복귀하는지가 최소 비용을 결정합니다.

그래서 (현재 도시, 방문 집합) 을 상태로 저장하면 같은 부분 문제를 한 번만 풀 수 있습니다.

3. 핵심 아이디어

상태 정의

dfs(cur, visited) = 현재 도시가 cur 이고, visited 에 포함된 도시를 이미 방문했을 때 남은 순회를 끝내는 최소 비용

기저 조건

모든 도시를 방문했다면 마지막으로 출발 도시로 돌아가야 합니다. 복귀 경로가 없으면 INF 를 반환해서 그 경로는 최소값 후보에서 빠지게 만듭니다.

점화식

dfs(cur, visited) = min(W[cur][nxt] + dfs(nxt, visited | (1 << nxt)))

4. 시각화

시각화 1. 핵심 상태를 표로 펼치면 분기가 한눈에 보인다

이 시각화는 한 상태에서 어떤 분기가 생기고 어떤 값이 저장되는지를 바로 읽히게 만드는 데 초점을 둡니다.

시각화 2. 같은 상태를 표로 풀어 쓰면 비교가 바로 된다

선택	총 비용	판정
2 → 3 → 4 → 1	29	보관 후보, 최적은 아님
2 → 4 → 3 → 1	25	이 상태의 정답

경로 A 계산: 2 → 3 비용 9, 남은 비용은 3 → 4 = 12, 4 → 1 = 8 이라서 총 29입니다.

경로 B 계산: 2 → 4 비용 10, 남은 비용은 4 → 3 = 9, 3 → 1 = 6 이라서 총 25입니다.

정리: dfs(1, 0011) = min(29, 25) = 25

시각화 3. 실제 예제 입력에서 마스크가 커지는 순서

단계	이동	마스크	의미
1	1 → 2 (+10)	0001 → 0011	1번, 2번 도시 방문 완료
2	2 → 4 (+10)	0011 → 1011	이 상태의 부분 문제 값이 25로 저장됨
3	4 → 3 (+9)	1011 → 1111	이제 모든 도시 방문 완료
4	3 → 1 (+6)	1111 유지	출발 도시로 복귀하며 최종 답 35 완성

5. 코드

Python

import sys
from functools import lru_cache

input = sys.stdin.readline
INF = 10 ** 15

n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
ALL_VISITED = (1 << n) - 1


@lru_cache(None)
def dfs(cur, visited):
    if visited == ALL_VISITED:
        if w[cur][0] == 0:
            return INF
        return w[cur][0]

    result = INF

    for nxt in range(n):
        if visited & (1 << nxt):
            continue
        if w[cur][nxt] == 0:
            continue

        cost = w[cur][nxt] + dfs(nxt, visited | (1 << nxt))
        result = min(result, cost)

    return result


print(dfs(0, 1))

6. 코드 해설

입력과 기본 준비

비용 행렬을 입력받고, 모든 도시를 방문했는지 확인할 비트마스크 ALL_VISITED 를 만듭니다.

메모이제이션 함수

@lru_cache(None) 로 같은 상태를 다시 계산하지 않도록 막습니다.

기저 조건

모든 도시를 방문한 순간에는 출발 도시로 돌아가는 비용만 확인하면 됩니다. 복귀할 수 없으면 큰 값 INF 를 반환합니다.

다음 도시 탐색

이미 방문한 도시와 길이 없는 도시를 제외하고, 가능한 모든 다음 도시를 확인하면서 최소 비용을 갱신합니다.

라인별 설명

아래 줄 번호는 위 코드 블록 기준입니다. 짧은 코드일수록 이런 식으로 흐름을 한 번 더 따라가면 구현 실수가 줄어듭니다.

줄	설명
1	import sys 빠른 입력을 쓰기 위해 sys 모듈을 불러옵니다.
2	from functools import lru_cache 같은 상태를 다시 계산하지 않기 위해 메모이제이션 데코레이터를 가져옵니다.
4	input = sys.stdin.readline 기본 input() 대신 더 빠른 입력 함수를 연결합니다.
5	INF = 10 ** 15 도달 불가능한 경우를 표시할 충분히 큰 값을 준비합니다.
7	n = int(input()) 도시 수를 입력받습니다.
8	w = [list(map(int, input().split())) for _ in range(n)] 도시 사이 이동 비용 행렬을 그대로 저장합니다.
9	ALL_VISITED = (1 << n) - 1 모든 도시를 방문했을 때의 비트마스크를 만듭니다. 예를 들어 n=4 이면 1111 이 됩니다.
12	@lru_cache(None) 같은 (cur, visited) 상태 결과를 캐시에 저장합니다.
13	def dfs(cur, visited): 현재 도시와 방문 집합을 받아 남은 순회 최소 비용을 반환하는 함수입니다.
14	if visited == ALL_VISITED: 모든 도시를 방문했는지 먼저 확인합니다. 이 조건이 기저 조건입니다.
15	if w[cur][0] == 0: 현재 도시에서 출발 도시로 돌아가는 길이 아예 없는 경우를 체크합니다.
16	return INF 복귀가 불가능하면 이 경로는 정답 후보가 될 수 없으므로 큰 값을 반환합니다.
17	return w[cur][0] 돌아가는 길이 있다면 그 비용을 그대로 반환합니다.
19	result = INF 현재 상태에서 만들 수 있는 최소 비용 후보를 큰 값으로 초기화합니다.
21	for nxt in range(n): 다음에 방문할 수 있는 모든 도시 후보를 순서대로 확인합니다.
22	if visited & (1 << nxt): 비트 연산으로 이미 방문한 도시인지 검사합니다.
23	continue 이미 방문한 도시라면 그 후보는 바로 건너뜁니다.
24	if w[cur][nxt] == 0: 현재 도시에서 다음 도시로 가는 길이 없는 경우를 걸러냅니다.
25	continue 갈 수 없는 도시 역시 후보에서 제외합니다.
27	cost = w[cur][nxt] + dfs(nxt, visited | (1 << nxt)) 현재 이동 비용과, 다음 도시로 넘어간 뒤 남은 순회를 끝내는 최소 비용을 더합니다.
28	result = min(result, cost) 지금까지 본 후보 중 가장 작은 값을 유지합니다.
30	return result 현재 상태에서 가능한 모든 다음 도시를 다 본 뒤 최솟값을 반환합니다.
33	print(dfs(0, 1)) 0번 도시에서 시작하고, 시작 도시만 방문한 상태로 탐색을 시작합니다.

7. 예제 따라가기

단계	현재 상태	선택	요약
1	(1, 0001)	1 → 2	누적 비용 10, 출발 직후 첫 이동
2	(2, 0011)	2 → 4	누적 비용 20, 3보다 4를 먼저 가는 선택이 유리함
3	(4, 1011)	4 → 3	누적 비용 29, 남은 도시는 3번 하나뿐
4	(3, 1111)	3 → 1	최종 비용 35, 출발 도시로 복귀하며 순회 완료

8. 복잡도

시간 복잡도: O(N² · 2^N)

방문 집합이 2^N 개이고, 각 상태마다 최대 N 개의 다음 도시를 검사합니다.

공간 복잡도: O(N · 2^N)

9. 마무리

이 문제는 비트마스크 DP의 전형적인 형태입니다. 상태 정의를 정확하게 잡고, 갈 수 없는 경우와 마지막 복귀 조건만 놓치지 않으면 안정적으로 구현할 수 있습니다.

한 줄 결론

외판원 순회는 현재 도시 + 방문 집합 을 상태로 잡는 비트마스크 DP 문제입니다.