[BOJ] 2098번 : 외판원 순회(TSP, BitMask, DP, DFS)

접근

으아아아아아!!! 진짜 오래 걸렸다. 접근 자체는 너무 유명한 문제라 간단하게 했는데 최적화하는 과정에서 2일은 잡아먹었다.

외판원을 잡아다가 그냥 알아서 좀 가라고 너무 말하고싶었다...

 

결론은 DFS로 갈 경로를 정하고, BitMask로 지금까지 방문했던 도시를 저장한다. 또한 DP를 이용해서 해당 도시 방문의 최소비용을 저장하여, 효율성을 높인다.

 

앞서 해결했던,

2023.12.31 - [알고리즘(Algorithm)] - [BOJ] 1562번 : 계단 수(DP, BitMask) 문제에서 설명했듯이, BitMask 방법론은 너무 큰 N에 대해선 공간 효율면에서는 맞지않을 수 있다고 말했다.

하지만 이 문제는 N이 16정도로 별로 크지 않기 때문에 BitMask를 사용해볼 수 있다.

BitMask 이론에 대한 내용은 위의 계단 수 문제 아티클을 참고하자.

해결

이 문제에서 사용되는 인자는 아래와 같다.

• ` N ` : 도시의 갯수

BitMask를 활용하기 위해서, 먼저 DP 테이블을 만들어주자.

DP 테이블의 Shape은 `(N, 2^N)`이다.

의미는 도시 `N`의 방문상황(`2^N`가지)에 대한 최소 비용을 저장하기 위함이다.

 

TSP문제는 결국 최소 비용의 순환 경로가 정해져있다면, 어디서 시작하든 해당 경로를 따라갈것이란 것을 전제로 수행된다.

예를 들어

`0 -> 2 -> 3 -> 1 -> 4 -> 0` 이 최소 순환 경로라면, `3 -> 1 ->4 -> 0 -> 2 -> 3` 이렇게 탐색해도 같은 최소 비용을 가질 것이라는것.

그럼으로 시작점은 자유롭게 잡아도 괜찮다. 나는 편의를 위해 0에서 시작했다.

(+코드에는 어디서 시작하든 상관없이 st 변수에 표현해주겠다.)

(++ 근데 제출은 st를 0이나 1로 고정하고 해결하라. `N <= 2` 인덱스 에러 발생할 수도 있어서)

 

모든 도시의 방문을 진행하면서, DFS로 도시들을 방문한다.

해당 도시를 방문할 때는 BitMasking을 이용해서(visited | (1<<k)) 방문여부를 표시하고 탐색을 진행한다.

최솟값을 갱신해나가며, DP 테이블에 해당하는 도시의 방문여부에 따라 업데이트를 진행한다.

자세한 설명보다는 역시 코드를 보는게 더 이해가 쉬울 것이니, 코드를 보고 나머지 이해를 진행하자.

 

그것보다 내가 해결하는데, 시간이 오래 걸린 것에 대해서 말을 이어나가보자.

일반적으로 최소비용을 구하기 위해서, DP 테이블을 초기화할 때 INF 값으로 초기화를 진행한다. 나만 그럴지 모르겠지만..

 

만약 어떤 특정 방문이 불가능한 케이스가 있다고 생각해보자.

예를 들어, dp[2][00111] => 에서 이제 도시 2를 방문하고, 3, 4 를 방문하고나서,

3, 4에서 시작지점 0으로 가는 경로가 없다면, dp[3][11111], dp[4][11111] = INF 값을 반환할 것이다.

그럼 DP 테이블 자체를 INF로 초기화 했었기 때문에, 방문은 했는데 경로가 없어서 INF가 된건지, 원래 초기화값인건지 구분을 하지 못해서, 매번 dp[3][11111], dp[4][11111] 케이스가 나올 때마다 dfs를 수행하게 될 것이다. 그래서 아마 55 ~ 58%에서 시간 초과가 뜰 것이다.

 

이 문제를 해결하기 위해선, [초기화 값 / 경로 방문 실패]에 대한 값을 구분지어줄 필요가 있다.

따라서 초기화 값을 다른 특정 이상한 값(코드에선 -1)로 설정하고, 경로 방문 실패 시에 INF를 반환해줌으로써, 최적화를 진행했다.

 

이 문제에 대한 해설을 검색했을 때 많은 블로그들이 예전에 작성하고 수정을 안해서인지 그냥 INF초기화 코드가 많이 올라가 있는데, 내 글이 해당 에러를 해결하는데 많은 도움이 되면 좋겠다.

코드

import sys

input = sys.stdin.readline

N = int(input())
costs = [list(map(int, input().split())) for _ in range(N)]
st = 1
dp = [[-1] * (1 << N) for _ in range(N)] # 초기화 값 -1

def tsp(i, visited):
    # Code
    if visited == (1 << N) - 1: # 모든 도시 방문했다면 1111...1(N개) - 1
        return costs[i][st] if costs[i][st] else float('inf') # 출발지(0)으로 방문하는 경로가 있다면, 비용을 반환 아니면 INF
    
    if dp[i][visited] != -1: # 최솟값 계산되어 있으면, 반환
        return dp[i][visited]
        
    ret = float('inf') # 최소 비용 경로를 선택하기 위한 변수 -> 가장 처음엔 INF로 초기화
    for k in range(N): # 모든 도시 방문 체크
        if k == st or not costs[i][k] or visited & (1 << k): # i -> k로 가는 경로가 없으면, 혹은 이미 방문했으면
            continue
        
        ret = min(ret,
                 tsp(k, visited | (1 << k)) + costs[i][k]) # 최소 비용 경로를 찾는다. visited | (1 << k) 로 k 도시의 방문여부 표시
    
    dp[i][visited] = ret # 위에서 갱신된 최소 비용경로로 업데이트 해준다.
    return dp[i][visited]


print(tsp(st, 1<<st))