백준 : 2098 외판원 순회

백준 : 2098 외판원 순회

문제 분석

비트마스크와 DP를 이용해 모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최소 비용을 구하는 문제로, 방문 상태를 비트마스크로 관리하면서 현재 도시와 방문 경로를 기반으로 dp 테이블을 갱신해 최적 경로를 찾는다.

비트마스크 활용

n = 도시 개수

비트마스크를 사용하여 0과 1로 도시 n개의 방문 여부를 관리한다.

비트마스크는 도시 개수 n만큼의 자리수를 가지는 이진수로 표현된다.

예시: 0111

비트마스크를 읽는 방법은 오른쪽 → 왼쪽 이다.

(오른쪽이 출발 도시, 왼쪽으로 갈수록 번호가 높은 도시)

• 0 : 도시 3 방문 안 함
• 1 : 도시 2 방문함
• 1 : 도시 1 방문함
• 1 : 도시 0 (출발지) 방문함 (시작 시 초기 세팅)

tsp(visited, current) 에서 초기 호출은 tsp(1, 0) 이다.

여기서 visited = 1 은 이진수로 0001, 즉 0번 도시만 방문한 상태를 의미한다.

자기 자신을 방문했다고 표시하는 이유

문제는 "모든 도시를 한 번씩 방문하고 출발 도시로 다시 돌아오는 최소 비용"을 요구한다.

따라서 출발 시에 이미 출발 도시를 방문했다고 처리해야 올바르게 방문 횟수를 관리할 수 있다.

시작 도시는 반드시 언젠가 돌아올 예정이므로, 출발할 때 미리 방문했다고 표시한다.

다시 돌아오지 못하더라도 이 방문 처리는 변하지 않고 그대로 유지된다.

Top-Down : 시간초과

재귀와 메모이제이션으로는 55% 에서 시간 초과로 넘어가지 못했다. for문에서 next_city를 돌면서 tsp를 호출하고, visited 가 4개 도시 중 2개만 켜진 상태에서 동일한 visited + current 조합이 서로 다른 경로로 여러 번 재귀 호출 된다. 메모이제이션으로 저장하더라도, 저장하기 “전까지” 중복 호출이 발생해서 시간 초과가 난다.

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
# 도시 n개에 따라 방문 여부 2**n가지로 표현 가능 (이진수)
dp = [[INF]*n for _ in range (1 << n)]

def tsp (visited, current):
        # 종료 조건
    if visited == (1 << n) - 1 :
        return cost[current][0] or INF
    # 메모이제이션
    if dp[visited][current] != INF :
        return dp[visited][current]

    for next_city in range(n):
        if visited & (1 << next_city) or cost[current][next_city] == 0 :
            continue
        dp[visited][current] = min(
            dp[visited][current],
            tsp(visited | (1 << next_city), next_city) + cost[current][next_city] 
        )
    return dp[visited][current]

print(tsp(1, 0))

코드 분석

1. 종료 조건 : 모든 도시를 방문했으면 출발지로 돌아가는 비용 반환

if visited == (1 << n) - 1 :

• ✔️ 모든 도시를 방문했는지 확인
• n = 4 일때 ( 1 << n ) 은 10000
• 10000 - 1 = 01111
• 즉 visited의 숫자가 모두 1일때, 모든 도시를 방문했다고 생각한다.

return cost[current][0] or INF

• cost[current][0] : 현재 도시에서 출발지로 가는 비용
• 만약 길이 없으면 or INF를 사용하도록 설정

2. 메모이제이션 : 한번 계산한 값은 다시 계산하지 않는다

if dp[visited][current] ≠ INF : return dp[visited][current]

✔️ 이미 계산한 상태면 바로 반환

3. 다음 도시 탐색

for next_city in range(n)

다음으로 갈 수 있는 도시 후보들을 전부 다 확인한다

4. 가지치기 (방문 여부 & 길 존재 여부 확인)

if visited & (1 << next_city) or cost[current][next_city] == 0

여기서 체크하는 2 가지

1) 이미 방문했는지?
- visited & ( 1 << next_city )
- visited 에서 next_city 비트가 켜져있으면 건너뛴다 (방문함)
2) 길이 존재하는지?
- cost[current][next_city] == 0
- current 에서 next_city로 가는 길이 있는지?
- 길이 없다면 (가중치 0) 이동 불가하니 건너뛴다

✅ 둘 중 하나라도 참이라면 continue로 다음 도시를 검사한다

5. 비용 계산 및 dp 테이블 갱신

dp[visited][current]

다음 도시로 이동했을때 비용을 계산하고, 현재 최소 비용과 비교해서 업데이트 한다

검사하는 조건

1) visited | (1 << next_city)
- visited를 업데이트하고 next_city를 방문했다고 기록한다
- 비트 OR 연산으로 방문 표시를 추가 ( | = OR )
2) tsp(새로운 visited, next_city)
- 재귀 호출로 다음 도시로 이동해서 남은 경로 비용을 계산한다
3) cost[current][next_city]
- 현재 도시에서 다음 도시로 이동하는 비용

✅ 현재의 최소 비용과 비교해서 더 작은 값으로 업데이트 한다

Bottom-up : 통과

import sys
input = sys.stdin.readline

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
# 도시 n개에 따라 방문 여부 2**n가지로 표현 가능 (이진수)
dp = [[INF]*n for _ in range (1 << n)]
dp[1][0] = 0    # 출발: 도시 0에서 시작하고, 방문 기록은 도시 0만 방문한 상태

def tsp (visited, current):
    for visited in range((1<<n)):
        for current in range (n):
            if dp[visited][current] == INF :
                continue
            for next_city in range (n):
                if visited & (1 << next_city) : 
                    continue
                if cost[current][next_city] == 0 :
                    continue
                next_visited = visited | (1 << next_city)
                dp[next_visited][next_city] = min (
                    dp[next_visited][next_city],
                    dp[visited][current] + cost[current][next_city]
                )
    return dp[visited][current]

tsp(1, 0)

visited_all = (1<<n) - 1 
answer = INF
for city in range(n):
    if cost[city][0] == 0 :
        continue
    answer = min (answer, dp[visited_all][city] + cost[city][0])
print(answer)

코드 분석

DP 테이블 채우기 (탐색)

탐색은 바텀업 방식으로 진행한다.

1. for visited in range((1 << n)) : 방문 상태를 모두 순회한다.
2. for current in range(n) : 현재 도시를 순회한다.
3. if dp[visited][current] == INF : 아직 도달하지 못한 상태면 스킵한다.
4. for next_city in range(n) : 다음으로 이동할 도시 후보들을 모두 검사한다.
5. 가지치기 조건으로 두 가지를 확인한다.
   • 5-1. visited & (1 << next_city) : 이미 방문한 도시는 패스
   • 5-2. cost[current][next_city] == 0 : 현재 도시에서 next_city 로 가는 길이 없는 경우 패스
6. 다음 방문 상태는 next_visited = visited | (1 << next_city) 로 갱신한다.
7. dp 갱신은 dp[next_visited][next_city] = min(dp[next_visited][next_city], dp[visited][current] + cost[current][next_city]) 으로, 기존 값과 현재 경로의 비용을 비교하여 최소값으로 업데이트한다.

최종 정답 계산

1. 모든 도시를 방문한 상태는 visited_all = (1 << n) - 1 로 나타낸다.
2. for city in range(n) 으로 마지막 도시를 순회하면서
3. answer = min(answer, dp[visited_all][city] + cost[city][0]) 로 최소 비용을 구한다.
4. 출력은 print(answer) 로 수행한다.

Bottom-Up + BFS (큐) : 통과

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
dp = [[INF]*n for _ in range (1 << n)]

# 큐 초기화
queue = deque()
dp[1][0] = 0
queue.append((1, 0))

# 큐가 빌때까지 반복
while queue :
    visited, current = queue.popleft()
    # 다음 도시를 탐색
    for next_city in range(n):
            # 이미 방문했으면 패스
        if visited & (1 << next_city):
            continue
        # 길이 없으면 패스
        if cost[current][next_city] == 0 :
            continue
        # 새로운 visited 갱신
        next_visited = visited | (1 << next_city)
        # 새로운 비용 계산
        new_cost = dp[visited][current] + cost[current][next_city]
        # 새로운 비용이, 기존 비용보다 작으면 dp를 갱신하고 큐에 추가
        if dp[next_visited][next_city] > new_cost :
            dp[next_visited][next_city] = new_cost
            queue.append((next_visited, next_city))

answer = INF
visited_all = (1 << n) - 1
# 모든 도시를 방문한 상태에서 출발 도시로 돌아오는 비용 확인
for city in range(n):
    if cost[city][0] == 0 :
        continue
    answer = min(answer, dp[visited_all][city] + cost[city][0])
print(answer)

비트마스크 DP 를 활용해서 외판원 순회 문제를 해결하는 방식 중 하나는 "큐를 사용하여 visited 상태를 확장" 하는 방법이다. 기존 bottom-up 방식에서는 for visited ~ 으로 순서를 정해준 방법과의 차이점이다.

코드 분석

큐를 이용하면, next_visited 를 큐에 추가하면서 visited 가 커지는 방향으로 탐색할 수 있다.
이 과정은 BFS 와 유사하다. 상태 공간을 넓혀 가면서 점점 visited 비트가 더 많이 켜진 상태로 확장한다

시간복잡도

• 다만 기존의 bottom-up 방식보다는 더 느리다.
• 탑-다운 방식의 중복 호출을 제거했지만, 큐 연산 오버헤드 + 메모리 접근이 이루어지기 때문이다.
• 큐에서 상태를 pop (O(1))
• 다음 상태를 append (O(1))
• push/pop의 cost가 누적되고, 이 과정이 메모리 locality가 떨어진다.
• 이론적으로는 시간 복잡도는 O(n^2 * 2^n)으로 동일.

1. 초기 상태:
   • visited = 0001 (도시 A 만 방문)
   • current = A
   • dp[visited][current] = 0
   • 큐에 (visited, current) 를 추가
2. 큐가 빌 때까지 반복:
   • 큐에서 상태 (visited, current) 를 pop (O(1))
   • visited 에서 갈 수 있는 next_city 를 모두 탐색
   • next_visited = visited | (1 << next_city) 로 방문한 도시를 추가
   • new_cost = dp[visited][current] + cost[current][next_city]
   • 만약 new_cost 가 현재 dp[next_visited][next_city] 보다 작으면, dp 를 갱신하고 큐에 push
3. 탐색 방향:
   • 큐에 next_visited 를 넣으면서 visited 비트가 점점 켜지는 방향으로 확장
   • visited = 1111 (모든 도시 방문) 상태까지 큐에 쌓인다
   • visited = 1111 인 상태는 여러 번 큐에 들어가지만, dp 테이블은 "최소 비용" 으로만 갱신되므로 불필요한 갱신은 일어나지 않는다.
4. 최종 정답 구하기:
   • visited = 1111 (모든 도시 방문) 상태에서 마지막 도시 city 를 for 문으로 순회
   • dp[visited_all][city] + cost[city][0] 로 출발 도시로 돌아오는 비용을 계산
   • answer = min(answer, 위의 값)
   • for 문을 다 돌고 나면 answer 에는 최소 비용만 남는다

While 문의 경로 탐색

결론 : dp[1111][C] 인 경우가 최소 경로로 채택된다.

이때 마지막 A → … → C → A 로 갈 수 있는 경로는 노란색으로 표기해 둔 경로가 있다.

A → B → D → C → A 로 가는 경우

A → D → B → C → A 로 가는 경우

이 중 비용이 최소인 경우는 첫 번째로 답인 35를 도출할 수 있다.