[백준/C++] 2098번 외판원 순회

백준

---

🤔문제 이해

모든 도시를 거치고 다시 처음 도시로 돌아오는 모든 경로 중 비용이 가장 적게 드는 경로의 비용을 구하는 문제이다.

---

💡첫번째 아이디어

 

그냥 순열을 구해서 풀면 최대 16! =20,922,789,888,000으로 1초 안에 절대 풀 수 없다.

이 문제는 1주차 스터디에서 배운 비트마스킹에 대한 문제였고, 문제 풀이 방식을 거의 다 배웠어서 DP와 비트마스킹으로 바로 풀 수 있었다.

물론 DP 동작 방식을 이해하기 위해 시간이 조금 걸리긴 했다.

 

 

🔥풀이🔥

dp[i][j]는 현재 위치 i와 현재까지 방문했던 정점들의 정보를 담은 j 값일 때, 앞으로 필요한 순회 비용의 최솟값을 의미한다.

j가 (1 << 정점의 개수) -1과 같으면 현재 모든 정점을 방문했다는 것을 의미한다.

각 정점에 대해 전부 방문했을 때의 최솟값을 찾으면 되므로 정답은 dp[처음 정점][1]이다.

 

---

아래는 제출한 코드이다.

#include <iostream>
#include <cmath>

using namespace std;
#define MAX 1000000000;

int dp[17][65537];
int w[17][17];
int n;

int solve(int cur, int visit) {
    if (visit == (1 << n) - 1 && w[cur][0])
        return w[cur][0];

    if (dp[cur][visit]) return dp[cur][visit];
    dp[cur][visit] = MAX;

    for (int i = 1; i < n; i++) {
        if (visit & (1 << i)) continue;
        if (!w[cur][i]) continue;
        dp[cur][visit] = min(dp[cur][visit], solve(i, visit | (1 << i)) + w[cur][i]);
    }
    return dp[cur][visit];
}


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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }
    cout << solve(0, 1);
}