[백준 / BOJ] 2098 외판원 순회

문제

출처 : www.acmicpc.net/problem/2098

2098번: 외판원 순회

외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고한다. 이때, 이미 방문한 도시는 재방문할수없다. 도시를 이동할때 일정한 비용이 필요할때, 외판원이 모든 도시를 거쳐 출발도시로 돌아오는 최소 비용을 구하는 문제다.

 

풀이

완전탐색으로 풀려고할경우, N이 최대 16이므로, 16 * 15 * 14 * 13 * ... * 3 * 2 * 1 = 16! 이라 시간초과가 난다.

다이나믹 프로그래밍으로 풀어야하는문제였다.

각 도시의 방문상태를 체크해줘야하는데, 도시의 개수가 16개라 비트마스킹으로 체크해줘야한다.

 

문제를 풀기전에 주의할점이있었는데(이것때문에 몇번틀림), 어느 경로로 가던지, 1번도시는 가장 마지막에 도달해야한다는것이다. 따라서, 최소경로로 모든 도시를 순회하고 마지막에 1번도시로 가는 경로가 없다면, 해당 경로는 절대 답이될수없다.

 

체크배열을 이용해, 이전에 방문했던 상태를 재방문하지 않도록 처리해줘야한다.

check[방문상태] = 최소비용

 

이때, 방문 상태를 비트마스크를 이용해 체크해준다. 예를들어, 1번도시 2번도시 3번도시를 방문했다면, 방문상태는 0000000000000111 이 된다. 또, 이때 최소 비용이 5가 들었다면

check[0000000000000111] = 5 가 된다.

 

체크 배열을 이렇게만해서 풀경우 틀렸습니다를 받게되는데, 다음 상태에 저장된 최소 비용보다 더 많은 비용을 들여 다음 상태에 도달했더라도, 도달 도시가 다를수있기때문에, 나중엔 비용이 더 작아질수 있기때문이다. 따라서, 도달도시를 나타내주기위해 2차원으로 체크해줘야한다.

check[마지막 도달 도시][해당 도시에 도달했을때 방문상태] = 최소비용

 

마찬가지로 1번도시 2번도시 3번도시를 순서대로 방문했을때의 체크배열을 나타내면,

check[3][0000000000000111] = 5 가 된다.

 

위 정보를 갖고 구현하면되는데, DFS로 구현할경우 시간초과가 날수있다. (최악의 경로순서로 방문했을때, 결국 모든 경로를 다 볼수도있음)

시간초과 소스코드

//
// xb205
// 2021.01.29
//
#include <iostream>
#include <algorithm>
using namespace std;
int N, check[17][1 << 17], arr[17][17];

int getcost(int idx, int bit, int cnt){
    int cost = check[idx][bit];
    if(cnt != N){
        cost = 2000000000;
    }
    for(int i = 1; i <= N; i++){
        int _bit = bit | (1 << (i-1));
        int _num = check[idx][bit] + arr[idx][i];
        if((cnt < N-1 and i == 1) or arr[idx][i] == 0 or bit & (1 << (i-1)) or (check[i][_bit] > 0 and check[i][_bit] <= _num)) continue;
        check[i][_bit] = _num; 
        cost = min(cost, getcost(i, _bit, cnt+1));
    }
    return cost;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> arr[i][j];
        }
    }
    cout << getcost(1, 0, 0) << "\n";
    return 0;
}

 

처음에 DFS로 구현했다가 시간초과가 나길래 BFS로 고쳐서 제출했더니 맞았다. 

 

구현은 일반적인 BFS와 크게 다르지않다. BFS안의 탐색 조건을 정리해보면,

1. 현재 탐색 도시 수가 N-1보다 작을때, 1번도시를 방문할려 할경우 continue;

2. 다음 도시로 가는 경로가 없을경우 (다음도시로 가는 비용이 0일경우) continue;

3. 이미 다음 도시를 방문했을경우 (비트마스크 이용) continue;

4. check[다음도시][방문상태]가 더 작을경우 continue;

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2098%20%EC%99%B8%ED%8C%90%EC%9B%90%20%EC%88%9C%ED%9A%8C/main.cpp

devxb/JJUNalgo