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

문제 링크

성공 여부(걸린 시간): 실패 (1시간)

아이디어

기본 외판원 순회 개념 문제이다(TSP). 작년에 알고리즘 수업때 대충듣고 뭐 이정도까지 나오겠어 하고 안풀고 있다가 어제 계단수찾기 문제에서 피를 보고 해당 개념에 대해서 익숙해지기 위해서 노력중이다. 사실 개념적으로는 그렇게 어려운 문제는 아니나 실제로 코드를 구현할 수 있냐 없냐는 또 다른 문제이기 때문에 풀어보았다.

아니라 다를까 1시간동안 풀었으나 실패했다. 이유는 디테일한 부분들을 놓친게 너무 많았기 때문.

 

우선 외판원 순회는 외부판매원이 모든 노드들을 거쳐 다시 자신의 노드로 돌아오기까지 걸린 비용의 최소를 구하는 문제인데
이를 하기 위해서는 각 방문에 대한 비트마스킹을 통해서 해당 상태에 대한 가중치값을 저장해주어야 한다.

DFS로 한다면 할 수는 있으나 노드들이 조금만 많아지더라도 재귀 호출이 어마어마하게 많아지므로 DP로 푸는 것이 적어도 이 문제에서는 타당하다.

 

우선 배열은 두 개를 선언했다.

dp, W

W 배열에서는 가중치에 대한 정보를 받아와서 저장해주었고

dp 배열에서는 [방문처리][현재 노드] 이러한 방식으로 해당 상태까지 도달하는데 든 최소의 가중치를 저장해준다.

 

그리고 코드의 흐름은 이러하다.

1. 0에서 출발해서 나머지 모든 노드들을 방문하는 dp배열에 대한 갱신

2. 0으로 다시 돌아오는 갱신 cur -> 0

 

왜 시작점에 대한 정보가 없는데 0으로 했냐?

-> 어차피 외판원 순회에서는 모든 노드들을 방문해야 하고 또한 자신의 노드로 돌아와서 끝나기 때문에 어디서 출발하던 상관없음

 

for (int mask = 0; mask < (1 << N); mask++) {
	for (int cur = 0; cur < N; cur++) {
		if (dp[mask][cur] == INF_MAX || (mask & (1 << cur)) == 0) {
			continue;
		}
		for (int next = 0; next < N; next++) {
			if (W[cur][next] == 0 || (mask & (1 << next)) != 0) {
				continue;
			}
			int visited = mask | (1 << next);
			dp[visited][next] = min(dp[visited][next], dp[mask][cur] + W[cur][next]);
		}
	}
}

 

만약 dp[mask][cur]이 갱신된 적 없다면 다음 반복문으로 바로 넘기게 되는데 그 이유는 

그 값이 갱신된 적 없다는 뜻은 아직 도달한 적이 없다는 뜻이고 

그렇다면 next도 불가능하기 때문이다. (mask & (1<<cur)이 0인 경우도 방문한 적이 없다는 뜻)

 

그리고 그 다음 next 반복문에서는 W[cur][next]값이 0이다? -> 그냥 못간다는 얘기 

방문한적 없으면 continue하던 이전 cur 반복문 단에서와는 반대되게 간적있으면 넘긴다.

왜냐하면 갈 수가 없으니까!

 

그렇게 도착했을때 해당 dp [next에 대한 방문을 추가로 처리해준 비트마스크][다음 노드]와

현재까지의 방문하는데 까지의 dp값과 다음으로 이동하는 가중치의 합 중에서 최소로 갱신해준다.

 

그다음에는 각 마지막 방문지에서 복귀하는 것에 대해서 갱신을 해주고 

그 중에서 최소값을 마지막에 출력하면 끝이다.

풀이 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    int INF_MAX = 0x7f7f7f7f;
    cin >> N;

    int N_MAX = (1 << N) - 1;

    vector<vector<int>> dp(1ULL << N, vector<int>(N, INF_MAX));
    vector<vector<int>> W(N, vector<int>(N, 0));

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

    dp[1 << 0][0] = 0;
    for (int mask = 0; mask < (1 << N); mask++) {
        for (int cur = 0; cur < N; cur++) {
            if (dp[mask][cur] == INF_MAX || (mask & (1 << cur)) == 0) {
                continue;
            }
            for (int next = 0; next < N; next++) {
                if (W[cur][next] == 0 || (mask & (1 << next)) != 0) {
                    continue;
                }
                int visited = mask | (1 << next);
                dp[visited][next] = min(dp[visited][next], dp[mask][cur] + W[cur][next]);
            }
        }
    }
    int answer = INF_MAX;
    for (int cur = 0; cur < N; cur++) {
        if (W[cur][0] == 0 || dp[N_MAX][cur] == INF_MAX) {
            continue;
        }
        answer = min(answer, dp[N_MAX][cur] + W[cur][0]);
    }
    cout << answer;
    return 0;
}