[백준/Baekjoon] 2098 외판원 순회 C++ :: Dynamic Programming

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

2098번: 외판원 순회

---

1. Logic

외판원 순회란 도시들(노드)이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌도 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제이다.

 

아래 그래프를 보자. 

이 5개의 노드가 있을 때 순회를 할 수 있는 방법은 총 5가지이다. 

1 > 2 > 3 > 4 > 5

2 > 3 > 4 > 5 > 1

3 > 4 > 5 > 1 > 2

4 > 5 > 1 > 2 > 3

5 > 1 > 2 > 3 > 4

위의 간단한 설명에서 말했듯이 불특정한 도시에서 시작해서 돌아오는 방법으 ㄹ나누는 시작점은 어떤 도시를 출발 도시로 잡을 것이냐이다. 사실 어떤도시를 출발도시로 잡아도 상관이 없는데, 어떠한 도시를 출발도시로 하던지 다시 출발도시로 돌아오는데 드는 최소 비용은 같다. 

 

이처럼 외판원 문제의 최소 비용을 구하기 위해서는 DFS를 사용하여 1번 도시부터 방문하지 않은 도시들을 방문하고 출발도시까지 도달 했을 때 드는 비용들을 구한 뒤 그중 최소 거리를 구하면 된다.

1번 도시를 출발지점으로 잡고 순회를 한다고 가정한다. 

1번도시에서 5번도시를 먼저 도는 경로와 2번도시를 먼저 방문하는 경로를 나타냈을 때 아래의 그림과 같이 된다.

이 두개의 경로를 자세히 보면 곂치는 경로가 존재한다. 

3 > 4 > 1로 가는 경로를 중복해서 계산하게 된다. 이 과정을 DP적으로 생각해보면 3번과 4번 도시를 방문하지 않고 3번에 서 이전에 계산된 최소 비용을 저장해 두면 계속 계산하지 않고 계산된 값을 리턴하여 계산량을 줄일 수 있다.

 

다시 문제로 돌아와서 이 문제에서는 dp테이블을 정할 때 dp[현재 위치한 도시][이미 방문한 도시]를 뜻하며 값은 남은 도시를 모두 돌아 출발 도시로 오는 최솟값을 저장하는 배열이다.

다만 이미 방문한 도시를 표현할 때 비트마스킹을 통해 표현하는데 [1<<16]이란 2^16과 같은 뜻이다. 

1~5번 까지의 마을이 존재할 때 이전에 방문한 도시를 dp[2][1]같은 방법으로 저장하게 되면 4byte를 저장하는 만큼의 메모리가 필요하기 때문에 매우 비효율적이다. 그래서 Bitmasking을 통해 integer number로 저장하여 1에 위치해있으면 0001이렇게 표현을 한다. 그럼 0011은 2에 위치했다는 것을 알 수 있다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n;
int dp[16][1<<16]; //2^16
int input[16][16];

int dfs(int cur, int vis) {
    //기저 조건
    if(vis == (1 << n) - 1) {
        if(input[cur][0] == 0) {
            return INF;
        }
        return input[cur][0];
    }

    int &ret = dp[cur][vis];

    if(ret != -1) return ret;

    ret = INF;

    for(int i = 0; i < n; i++) {
        if(input[cur][i] == 0) //길이 없으면
            continue;
        if((vis & (1<<i)))
            continue;
        ret = min(ret, dfs(i, vis | 1<<i) + input[cur][i]);
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;

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

    memset(dp, -1, sizeof(dp));

    cout << dfs(0, 1);
    
}

 

 

---

3. Feedback

외판원 순회문제를 풀면서 비트마스킹에 대해서도 접하게 됬는데 조금 더 깊에 한번 알아봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐