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

 

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

 

https://www.acmicpc.net/problem/2098

---

 

 

해결전략

 

비트마스킹 Bitmasking

동적계획법 Dynamic Programming, DP

비트필드를 이용한 다이나믹 프로그래밍
외판원 순회 문제

---

 

 

정답 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n; // 도시의 수
vector<vector<int>> W; 
vector<vector<int>> dp;
const int INF = 2147000000;
 
int TSP(int cur, int visited)
{
    // visited의 모든 비트가 1이라면(즉, 모든 도시를 방문했다면), 현재 도시에서 시작 도시로 돌아가는 비용을 반환
    if (visited == (1 << n) - 1) {
        return W[cur][0] ? W[cur][0] : INF;
    }
 
    // 이미 계산된 적이 있는 경우 캐싱된 값을 반환
    int& ret = dp[cur][visited];
    if (ret != -1) return ret;
 
 
    ret = INF; // 초기값을 무한대로 설정
    for (int next = 0; next < n; next++) // 모든 도시에 대해
    {
    	// 아직 방문하지 않았고, 길이 있는 경우
        if (!(visited & (1 << next)) && W[cur][next] != 0) {
            // 현재 도시에서 다음 도시로 가는 비용 + 다음 도시에서의 최소 비용 계산
            ret = min(ret, TSP(next, visited | (1 << next)) + W[cur][next]);
        }
    }
 
    return ret; // 계산된 값을 반환하며, 동시에 dp[cur][visited]에 저장됨
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    W.resize(n, vector<int>(n));
    dp.resize(n, vector<int>(1 << n, -1));
 
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            cin >> W[y][x];
        }
    }
 
    int answer = TSP(0, 1);
    cout << (answer == INF ? -1 : answer) << endl;
 
    return 0;
}

 

visited | (1 << next)의 의미

• visited: 현재까지 방문한 도시들을 비트마스크로 표현한 값입니다.
• 1 << next
  • 1을 next 비트만큼 왼쪽으로 이동시킨 값.
  • 이는 next 도시를 방문했음을 의미하는 비트마스크다.
  • 예를 들어, next가 2라면 1 << 2는 0100(2진수).
• visited | (1 << next)
  • 현재 방문 상태인 visited에 next 도시를 추가로 방문했음을 기록한 새로운 비트마스크.
  • 예를 들어, visited가 1101이고 next가 1이라면, 1 << 1은 0010이 되고, visited | (1 << next)는 1101 | 0010이 되어 1111(2진수)가 됩니다. 이는 0번, 1번, 2번, 3번 도시를 모두 방문했음을 의미함.

 

+ W[cur][next]의 의미

• W[cur][next]
  • 현재 도시 cur에서 다음 도시 next로 가는 비용.
• TSP(next, visited | (1 << next)) + W[cur][next]:
  • TSP(next, visited | (1 << next)): next 도시를 방문한 후, 나머지 도시들을 모두 방문하는 최소 비용.
  • + W[cur][next]: 현재 도시 cur에서 next 도시로 가는 비용을 더한 전체 비용.

 

ret = min(ret, TSP(next, visited | (1 << next)) + W[cur][next])

 

현재 도시 cur에서 아직 방문하지 않은 도시 next로 이동한 후, 모든 도시를 방문하는 최소 비용을 계산

---