[정글 알고리즘]-[중]-백준 10971 외판원 순회 2

 

01 하노이 탑 📌 02 외판원 순회

실버 2 · DFS 백트래킹

[백준 10971] 외판원 순회 2
완전탐색 + 가지치기

cedis · 2026.03  |  Python · DFS · 백트래킹 · 완전탐색

도시들을 한 번씩 방문하고 출발지로 돌아오는 최소 비용 경로를 찾는 문제다. 이름은 거창하지만 핵심은 단순하다. 모든 경우를 탐색하되, 쓸모없는 경로는 일찍 잘라낸다. 그게 바로 백트래킹 + 가지치기다.

🔗 문제 링크: 백준 10971번 - 외판원 순회 2
N개의 도시를 모두 방문하고 시작 도시로 돌아오는 최소 비용을 구하라.
W[i][j]: i→j 비용 (0이면 연결 안 됨). N ≤ 10

① 문제 이해: 그래프로 보기

N=4, 도시가 0~3번이라 하자. 인접행렬로 비용이 주어진다.

W	0	1	2	3
0	0	10	15	20
1	5	0	9	10
2	6	13	0	12
3	8	8	9	0

10/5 15/6 20/8 10/8 9/9 12/8 0 1 2 3 START (고정)

우리가 찾는 건 도시 0 → 도시 ? → 도시 ? → 도시 ? → 도시 0 으로 돌아오는 최소 비용 경로다.

② 핵심 아이디어 3가지

1

시작 도시를 0으로 고정한다

순환 경로에서는 어느 도시에서 출발해도 비용이 같다. 그러므로 시작점을 0으로 고정하면 탐색 범위를 1/N로 줄일 수 있다.

2

DFS로 모든 순열을 탐색한다

방문하지 않은 도시를 순서대로 DFS로 탐색하면 가능한 모든 경로를 탐색할 수 있다.

3

현재 비용이 최솟값을 넘으면 즉시 중단 (가지치기)

지금까지 쌓인 비용이 이미 알고 있는 최솟값보다 크거나 같으면, 이 경로는 답이 될 수 없다. 더 탐색할 필요가 없다.

③ 왜 시작 도시를 0으로 고정하나

순환 경로의 성질
0→1→2→3→0 와 1→2→3→0→1 은 같은 경로다. 단지 출발점이 다를 뿐이고, 비용은 동일하다.

N개 도시가 있을 때 출발점이 N가지가 있어도 모두 같은 경로를 중복 탐색하는 셈이다. 그래서 출발점을 0으로 고정하면 경우의 수가 N! → (N-1)! 으로 줄어든다.

N=10일 때: 10! = 3,628,800 → 9! = 362,880

탐색량이 10배 줄어든다

④ 가지치기: 핵심 최적화

✂️ 가지치기 조건

현재 누적 비용(cost)이 현재 알고 있는 최솟값(answer)보다 크거나 같으면 즉시 탐색을 중단한다.

if cost >= answer:
    returnPython

이게 왜 유효한가? 앞으로 어디를 가더라도 비용이 추가되기만 한다. 따라서 이미 answer 이상이면 앞으로도 절대 더 작아질 수 없다.

📌 탐색 경로 예시 (N=4, 도시 0 출발)

경로	누적 비용	결과
0→1→2→3→0	10+9+12+8 = 39	✅ 첫 후보 (answer=39)
0→1→3→2→0	10+10+9+6 = 35	✅ 더 작음 (answer=35)
0→2→... (cost≥35)	15 + ...	✂️ 가지치기
0→3→1→2→0	20+8+9+6 = 43	❌ 더 큼, 버림
최종 답	35	🏆 answer = 35

⑤ 한글 수도코드

N 입력
W ← N×N 인접행렬 입력
visited ← [False] * N
answer ← 무한대

함수 dfs(start, now, count, cost):

# 가지치기: 현재 비용이 이미 최솟값 이상이면 중단
만약 cost >= answer 이면
종료

# 모든 도시 방문 완료 시
만약 count == N 이면
# 현재 도시에서 출발 도시로 돌아갈 수 있는지 확인
만약 W[now][start] != 0 이면
answer ← min(answer, cost + W[now][start])
종료

# 다음 방문 도시 탐색
next를 0 ~ N-1 반복
만약 visited[next] 이면 건너뜀
만약 W[now][next] == 0 이면 건너뜀
visited[next] ← True
dfs(start, next, count+1, cost+W[now][next])
visited[next] ← False # 백트래킹

# 시작 도시 0 고정
visited[0] ← True
dfs(0, 0, 1, 0)
answer 출력

⑥ 코드 한 줄씩 분석

import sys
input = sys.stdin.readline         # ① 빠른 입력

N = int(input())
W = [list(map(int, input().split())) for _ in range(N)]   # ② 인접행렬

visited = [False] * N              # ③ 방문 여부
answer  = float('inf')            # ④ 초기 최솟값 = 무한대

def dfs(start, now, count, cost):
    global answer

    if cost >= answer:               # ⑤ 가지치기
        return

    if count == N:                   # ⑥ 모든 도시 방문 완료
        if W[now][start] != 0:       # ⑦ 출발지로 돌아갈 수 있는가
            answer = min(answer, cost + W[now][start])
        return

    for next in range(N):
        if visited[next]:   continue  # ⑧ 이미 방문한 도시
        if W[now][next] == 0: continue  # ⑨ 갈 수 없는 길

        visited[next] = True
        dfs(start, next, count + 1, cost + W[now][next])
        visited[next] = False         # ⑩ 백트래킹

visited[0] = True                   # ⑪ 시작 도시 고정
dfs(0, 0, 1, 0)
print(answer)Python

번호	코드	의미
①	sys.stdin.readline	input()보다 빠른 입력. 행렬 N×N을 받을 때 속도 차이가 남
②	W[i][j]	도시 i→j 이동 비용. 0이면 직접 연결 없음
③	visited	현재 경로에서 이미 방문한 도시를 표시
④	float('inf')	무한대. 비교 대상이 없을 때 초기값으로 사용
⑤	if cost >= answer	가지치기. 이미 최솟값 이상이면 탐색 불필요
⑥	if count == N	N개 도시를 모두 방문했을 때
⑦	W[now][start] != 0	현재 위치에서 출발 도시로 돌아가는 길이 있는지 확인
⑧	if visited[next]: continue	이미 경로에 포함된 도시는 건너뜀
⑨	W[now][next] == 0	연결이 없는 도시는 건너뜀
⑩	visited[next] = False	백트래킹: 이 도시를 다른 순서에서도 방문 가능하도록 복구
⑪	visited[0] = True	시작 도시 0을 고정. 중복 탐색 방지

⑦ 자주 하는 실수

실수 1: 마지막에 출발 도시로 돌아가는 길을 확인 안 함
count == N이 됐다고 끝이 아니다. 현재 도시에서 start로 가는 길 (W[now][start])이 0이면 이 경로는 완성되지 않는다.
반드시 W[now][start] != 0 조건을 확인해야 한다.

실수 2: 가지치기 순서를 잘못 배치
가지치기 조건 (if cost >= answer: return)은 반드시 count == N 검사 이전에 위치해야 한다. 순서가 바뀌면 가지치기 효과가 절반으로 줄어든다.

실수 3: 시작 도시 고정 안 함
visited[0] = True 없이 dfs(0, 0, 1, 0)을 호출하면, DFS 내부에서 도시 0을 다시 방문해 순환이 조기에 끊긴다. 시작 도시는 반드시 미리 방문 표시해야 한다.

⑧ 시간복잡도

최악: O((N-1)!) — N=10이면 약 36만 번

가지치기 적용 시 실제 탐색량은 훨씬 줄어든다

N ≤ 10이라 완전탐색이 가능하다.
N이 더 커지면 동적 프로그래밍(비트마스킹 DP)으로 풀어야 한다. (백준 2098번 - 외판원 순회 1)

🎯 핵심 정리

• 시작 도시를 0으로 고정해 중복 탐색 제거 → 탐색량 1/N
• 가지치기: cost >= answer이면 즉시 return
• 순환 경로: 마지막에 반드시 W[now][start] != 0 확인
• 백트래킹: DFS 후 visited[next] = False 복구
• 시간복잡도: 최악 O((N-1)!) — N≤10이므로 완전탐색 가능

· · ·

# 크래프톤정글 # 백트래킹 # DFS # 외판원순회 # 백준10971 # 실버2 # Python