BOJ 2098 : 외판원 순회 [C++]

 

2098번: 외판원 순회

 

싸피에서 알고리즘 배울 때도 틀렸던 문젠데, 또 틀렸다...

 

워낙 유명한 문제라 미트마스킹을 써야 한다는 건 알고 있었는데, 풀지 못했다

 

예전에 메모했던 것과 참고한 풀이(링크)를 보고 생각한 이 문제의 핵심은,

출발 위치를 고민할 필요가 없다는 것이다.

(처음으로 다시 돌아와야 한다는 것 > 사이클을 이룬다는 것 > 경로가 정해지면 사이클의 어느 도시에서 출발하든 비용은 같음 > 출발 위치를 고민할 필요가 없다)

 

dp 배열은 최대 도시 개수만큼 16 * (1 << 16) 개 크기의 2차원 배열로 생성했다.

dp[i][j] : i번 도시에 왔고, 현재 방문한 도시들은 j에 포함된 도시들이다.

 

출발 위치를 고민할 필요가 없기 때문에 0번 도시에서 출발한다고 가정하고 풀이했다.

그래서 종료조건을 '현재 도착한 곳을 도착함으로써 모든 도시를 방문했을 때'로 걸었고,

이때 현재 도착한 도시에서 0번 도시로 갈 수 있으면 경로가 완성되는 것이고, 그렇지 않다면 경로가 완성되지 못하도록 아주 큰 값을 반환했다.

 

 

코드

#include <iostream>

#define INF 987654321

int N;
int cost[16][16];
int dp[16][1 << 16];
int all_masked;

int tsp(int cur, int state) {
    if (state == all_masked) {
        if (cost[cur][0] == 0) {
            return INF;
        } else {
            return cost[cur][0];
        }
    }

    if (dp[cur][state] != 0) {
        return dp[cur][state];
    }

    dp[cur][state] = INF;
    for (int i = 0; i < N; i++) {
        if (cost[cur][i] == 0) {
            continue;
        }
        if ((state & (1 << i)) != 0) {	// 현재까지 방문한 도시 중에 i번 도시가 있다면 continue
            continue;
        }
        dp[cur][state] = std::min(dp[cur][state], tsp(i, state | (1 << i)) + cost[cur][i]);
    }

    return dp[cur][state];
}

int main() {
    std::cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            std::cin >> cost[i][j];
        }
    }

    all_masked = (1 << N) - 1;

    std::cout << tsp(0, 1) << "\n";

    return 0;
}