백준 2098번, 외판원 순회 풀이

문제

백준 2098번

풀이

DP 점화식을 $ dp[i][j] = i\ 정점에\ 방문했을\ 때\ j\ 정점들에\ 방문한\ 경우의\ 최솟값 $ 이라고 두겠습니다.

 

$ j $만큼 방문했다는 것은 어떤 정점들에 방문했는지에 대해서 기록해둔다는 의미입니다.

 

이 $ j $를 비트마스킹을 사용하여 처리할 것입니다.

일반적인 vector<bool> 등을 사용하여 처리할 수도 있지만, vector를 매번 재귀 함수의 매개변수로 넘겨주기에는 cost가 작지 않기 때문입니다.

 

$ j $를 이진수 정수로 두고 숫자 읽듯이 오른쪽부터 왼쪽 순서대로 읽을 겁니다.

그러면, 0번째 자리는 0번 정점에 방문했는지, 1번째 자리는 1번 정점에 방문했는지.. $ k $번째 자리는 $ k $번 정점에 방문했는지에 대한 정보를 담을 수 있습니다.

 

예를 들어서, $ 001011 $은 $ 0, 1, 3 $번째 정점에 방문했다는 의미가 됩니다.

 

$ n $의 범위가 16이므로 $ 2^{16} $은 충분히 정수형 내에서 처리할 수 있습니다.

 

그리고, 위 연산을 비트 연산자들을 활용하여 빠르게 처리할 수 있습니다.

이는 코드에 주석을 달아놨습니다.

 

이해가 안되거나 질문이 필요하면 언제든 댓글 달아주세요.

 

 

나머지는 구현은 재귀를 돌면서, dp table에 있으면 dp table에 있는 것을 리턴하고 그렇지 않으면 계속 매 정점에 갈 수 있는 정점으로 계속 가주는 재귀를 돌면서 풀 수 있습니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int dist[16][16], dp[16][131072], finish, n;

int solve(int current, int vis) {
    if (vis == finish)
        if (dist[current][0]) return dist[current][0];
        else return 1e9;

    if (dp[current][vis]) return dp[current][vis];

    int ret = 1e9;
    for (int j = 0; j < n; j++) {
        if (((vis >> j) & 1) == 0 && dist[current][j]) {
            //현재 정점과 j 정점이 연결되어 있고, j에 방문한 적이 없는 경우
            ret = min(ret, solve(j, vis | (1 << j)) + dist[current][j]);
        }
    }

    return dp[current][vis] = ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    finish = (1 << n) - 1; //모든 정점에 방문하면 1이 n만큼 채워져 있습니다.

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];

    cout << solve(0, 1);
}