[c++] 백준 #10971 외판원 순회 2

이번 문제는 TSP(Travelling Salesman Problem)이라 하여 굉장히 익숙한 내용을 다루는 문제이다. 

간단하게 내용을 요약해보자면, N개의 도시를 모두 다 방문하면서 처음 도시로 돌아가려고 할 때 가장 최소의 비용을 출력하는 문제이다.

 

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

<풀이>

나는 dfs + 비트마스킹으로 문제를 풀었다.

맨처음 시작지점을 1~N까지 모두 돌아가면서 dfs를 돌리면 된다. 너무 전형적인 dfs 풀이가 가능하다.

섬에 방문할 때마다 다음 섬을 이미 방문하지 않았으면서 && 간선이 존재하는 그런 곳으로 방문하면 된다.

마지막에 ending condition으로는 모든 섬을 다 돌았고, 처음 지점으로 간선이 존재하면 value를 리턴하게 하면 된다.

 

크게 어려울 것 없는 구현이지만, 내가 실수했던 부분은 다음 투어를 진행할 때 val을 미리 더해주고(주석처리한 부분) 함수를 호출해서 다음 도시를 확인할 때 문제가 생긴 것이다. 기본적으로 dfs 나 back tracking을 할 때에는 undo를 하는 과정을 고려해서 짜줘야하는데 그것을 실수했다. (visited를 표시하는 course 변수의 경우, 새로운 도시를 새로 visit한 이후에 call by value로 복사된 값을 변화시키기 때문에 문제가 되지 않는다.)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int cost[11][11];
int ans = INF;
int N;

int tour(int starting, int current, int course, int val){
    // set that we visited this city
    course |= (1 << current);

    // if we visited all city and there exists a way to comeback, return the value
    if(__builtin_popcount(course)==N && cost[current][starting]){
        val += cost[current][starting];
        return val;
    }
    

    int ret = INF;
    for (int i=1; i<=N;i++){
        // if already visited, continue
        if (course & (1 << i)) continue;

        else if (cost[current][i] && (i != starting)){
            //val += cost[current][i];
            ret = min(ret, tour(starting, i, course, val + cost[current][i]));
        }
    }

    return ret;
}

int main(){
    cin >> N;
    for (int i=1; i<=N;i++){
        for (int j=1; j<=N; j++){
            cin >> cost[i][j];
        }
    }

    for (int i=1; i<=N;i++){
        ans = min(ans, tour(i, i, 0, 0));
    }

    cout << ans << '\n';
    return 0;
}