[백준] 10971. 외판원 순회 2

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력

35

풀이

/* Date: 2020-09-29 */
#include <iostream>

using namespace std;

int N, Rst = 10000000000, Start;
int W[11][11];
int is_visit[11];

void init(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j<= N; j++){
            cin >> W[i][j];
        }
    }
}

void dfs(int curr, int cost){
    is_visit[curr] = 1;
    if(is_traverse_finish()){
        if(!W[curr][Start]){
            is_visit[curr] = 0;
            return;
        }
        cost = cost + W[curr][Start];
        if(Rst > cost) Rst = cost;
        is_visit[curr] = 0;
        return ;
    }
    for(int next = 1; next <= N; next++){
        if(is_visit[next]) continue;
        if(!W[curr][next]) continue;
        dfs(next, cost + W[curr][next]);
    }
    is_visit[curr] = 0;
}

int is_traverse_finish(){
    int ret = 1;
    for(int i = 1; i <= N; i++){
        if(!is_visit[i]) ret = 0;
    }
    return ret;
}

int main(){
    init();
    for(int i = 1; i <= N; i++){
        Start = i;
        dfs(i, 0);
    }
    cout << Rst << endl;
}

완전탐색문제였다.
is_visit 배열을 통해 방문 확인을 하는 메커니즘이 포인트라고 생각한다.
전역변수로 둔 Rst의 초깃값을 충분히 크게 주지 않아 서버에 돌렸을 때 바로 틀렸다고 나왔었다. (종종 까먹을 수 있으니 주의하기)

dfs의 경우 depth가 증감할 때마다 조정하는 값들이 있기 마련인데, 그런 값들을 조정하는 타이밍에 사각지대가 있을 경우 문제를 풀 수 없다.
내 풀이의 경우 is_visit 배열이 그 값에 해당한다. (cost는 따로 조정하지 않아도 되게끔 하였다.)

모든 도시가 다 방문이 된 상태에서 출발했던 도시로 갈 수 없는 상황에서 if(!W[curr][Start]) return을 하기 전에 is_visit[curr] = 0; 을 실행해 주지 않아 문제 통과가 안 되었고, 디버깅을 해서야 이 부분을 찾을 수 있었다. (푸는데 약 1시간 걸림..)

쉽게 생각하자면 depth가 증감할 때마다 함께 변하는 값들이 모든 branch에 대해 쌍을 이루고 있는지 확인하면 될 것 같다.
(e.g., dfs함수 시작 부분에 is_visit[curr] = 1 이 있으면 함수 내의 return statement 전에 is_visit[curr] = 0이 있는지 확인할 것)