← 블로그

· 알고리즘, 크래프톤 정글

[백준] 10971번: 외판원 순회 2 (Python/파이썬)

[백준] 10971번: 외판원 순회 2 (Python) - DFS와 가지치기 최적화

정글 1주차 마지막쯤 접한 문제인데, 하노이와 N-Queen의 벽을 넘고나니 이 친구가 기다리고 있었습니다. 처음 마주하고는 막막했는데 풀다보니 이해가 조금 생긴거 같아 부족하지만 공유해보려 합니다.

1. 문제 소개 및 분석

  • 문제 링크: https://www.acmicpc.net/problem/10971
  • 핵심 요약: 1번부터 N번까지의 도시를 모두 한 번씩만 방문하고, 원래 출발했던 도시로 돌아오는 가장 적은 비용을 구하는 문제입니다. (전형적인 외판원 순회 문제(TSP)입니다.)
  • 핵심 조건 분석:
    • 도시의 수 N이 2 이상 10 이하로 매우 작습니다.
    • 길이 없을 경우 비용은 0으로 주어집니다. (W[i][j] == 0)

2. 문제 접근 및 핵심 아이디어

  • 가장 먼저 주목해야 할 점은 N이 10 이하라는 조건입니다. N이 매우 작기 때문에, 모든 가능한 경로를 다 탐색해보는 완전 탐색(Brute-force) 접근이 가능합니다.
  • 이러한 모든 경로를 탐색하는 데 가장 적합한 알고리즘은 깊이 우선 탐색(DFS) 과 백트래킹입니다.
  • 여기에 두 가지 최적화 전략을 추가하여 불필요한 탐색을 줄일 수 있습니다.
    1. 시작점 고정: 어차피 모든 도시를 순회하는 사이클의 비용은 어디서 시작하든 동일합니다. (0->1->2->0 과 1->2->0->1의 비용은 같습니다.) 따라서 시작점을 0번 도시로 고정하여 중복 계산을 방지합니다.
    2. 가지치기 (Pruning): 탐색 도중, 현재까지의 비용이 이미 발견된 최소 비용(min_cost)을 초과하면, 그 경로는 더 이상 탐색할 가치가 없습니다. 해당 탐색을 즉시 중단하여 시간을 절약합니다.

3. 알고리즘 설계

고정된 시작점(0)에서 출발하는 DFS 함수를 재귀적으로 호출하여 모든 경로를 탐색합니다.

  • search(현재 도시, 방문한 도시 수, 현재까지의 비용)

DFS 동작 로직:

  1. 가지치기: 재귀 함수에 진입하자마자, 현재까지의 비용이 min_cost보다 크거나 같다면 즉시 함수를 종료(return)합니다.
  2. Base Case (재귀 종료 조건):
    • 모든 도시를 방문했다면 (방문한 도시 수 == N), 현재 도시에서 출발 도시(0번)로 돌아갈 수 있는지 확인합니다.
    • 돌아갈 수 있다면, (현재까지의 누적 비용 + 돌아가는 비용)을 계산하여 min_cost 와 비교 후 갱신합니다.
  3. Recursive Step (재귀 호출):
    • 모든 도시(nxt)를 순회하며 다음 방문할 도시를 찾습니다.
    • 조건:
      • 아직 방문하지 않은 도시인가?
      • 현재 도시에서 다음 도시로 가는 길이 있는가?
    • 위 조건을 만족하면, 해당 도시를 방문 처리하고, 누적 비용을 더해서 DFS를 재귀적으로 호출합니다.
    • 재귀 호출이 끝나고 돌아오면, 방문 처리를 해제하여 다른 경로를 탐색할 수 있도록 합니다. (백트래킹)

4. 코드 구현 (Python)

# 사용자님의 최적화된 코드를 바탕으로 작성되었습니다.
import sys

# 입력 처리
N = int(sys.stdin.readline())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [False] * N

# 결과값을 저장할 변수, 매우 큰 값으로 초기화
min_cost = float('inf') 

def search(curr, cnt, cost):
    global min_cost

    #  가지치기: 현재 비용이 이미 찾은 최소 비용보다 크면 더 이상 탐색하지 않음
    if cost >= min_cost:
        return

    # 모든 도시를 방문했다면
    if cnt == N:
        # 마지막 도시에서 출발 도시(0)로 돌아갈 수 있다면
        if W[curr][0] != 0:
            # 최종 비용을 계산하여 최솟값 갱신
            min_cost = min(min_cost, cost + W[curr][0])
        return

    # 다음 도시 탐색
    for nxt in range(N):
        # 아직 방문하지 않았고, 길이 있는 도시라면
        if not visited[nxt] and W[curr][nxt] != 0:
            visited[nxt] = True # 1. 방문 처리
            search(nxt, cnt + 1, cost + W[curr][nxt]) # 2. 재귀 호출
            visited[nxt] = False # 3. 백트래킹 (방문 처리 해제)

#  시작점을 0으로 고정하여 중복 탐색 방지
visited[0] = True
search(0, 1, 0)

print(min_cost)

5. 회고

  • 어려웠던 점: 처음에는 단순 DFS로 접근하여 시간 초과가 날 수 있다는 걱정이 있었지만, 문제의 제약 조건(N<=10)을 보고 완전 탐색이 가능함을 확신할 수 있었습니다.
  • 배운 점: 같은 완전 탐색이라도 가지치기와 중복 제거 로직을 추가하는 것만으로도 성능이 크게 향상될 수 있다는 것을 체감했습니다. 문제의 본질을 파악하여 불필요한 계산을 줄이는 것이 알고리즘 효율성의 핵심이라는 점을 다시 한번 배웠습니다.