[SW Expert Academy 1247번] 최적 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD 

SW Expert Academy

---

최적 경로 문제는 다이나믹 프로그래밍과 비트 미스킹으로 해결할 수 있습니다.

 

N이 최대 10이기 때문에, 경로의 모든 경우의 수를 계산하여 해결할 수도 있지만,

다이나믹 프로그래밍을 이용하면 시간을 단축시킬 수 있습니다.

 

TSP(Traveling Salesman Problem)

---

아래는 TSP 함수로,

현재 위치가 cur이고, 방문 상태가 visited일 때, 고객들을 모두 방문하고, 집으로 돌아가는 최소 비용을 반환합니다.

#define x first
#define y second
#define SIZE 12
#define INF 100000
int weight[SIZE][SIZE];
int d[SIZE][1<<SIZE];  // d[cur][visted]는 현재 cur이고, visted를 방문한 상태일 때, 고객들을 모두 방문하고, 집으로 돌아가는 최소 비용
int n;
pii st, en; // 회사, 집의 위치

int TSP(int cur, int visited){
    int &ret = d[cur][visited];
    if(ret != 0) return ret;

    if(visited == (1 << (n + 1))-1) {    // 모두 방문한 경우
        return weight[cur][n + 1];
    }

    ret = INF;
    for(int i = 0; i <= n; i++){
        if(visited&(1<<i)) continue; // 이미 방문한 경우
        // 방문하지 않은 경우
        ret = min(ret, TSP(i, (visited|1<<i)) + weight[cur][i]);
    }
    return ret;
}

 

TSP 함수 의 알고리즘은 아래와 같습니다. 

1. 이미 결과 값이 있는 경우 반환
2. 회사와 모든 고객을 방문한 경우, 현재 위치에서 집까지의 거리를 반환
3. 방문하지 않은 고객 nx가 있는 경우, (cur과 nx간의 거리 + (현재 nx이고, visited와 nx를 방문한 상태일 때 집으로 돌아가는 최소 비용)) 중 가장 작은 값을 반환

비트 마스킹

---

visited는 현재 어느 위치를 방문했는지 나타내는 정수입니다. 

예를 들어 10011₍₂₎인 경우, 0번, 1번, 4번 위치를 방문한 것을 나타냅니다. (회사는 0번, 집은 n + 1번 위치)

 

visited == (1 << (N + 1))-1로 회사와 모든 고객을 방문했는지 알 수 있습니다.

예를 들어 N이 5인 경우, 회사를 포함하여 6개의 위치를 방문해야합니다. (집은 마지막에 방문해야하므로 제외)

1 << (5 + 1)은 1000000₍₂₎이고, (1 << (N + 1)) - 1은 111111₍₂₎이 되어 회사와 모든 고객을 방문했음을 나타냅니다. 

 

또한, (visited & (1<<nx))로 nx가 이미 방문한 위치인지 확인할 수 있습니다.

예를 들어 visited가 10010(2)이고, nx가 2라면, (1 << nx)는 00100₍₂₎이 됩니다.

10010₍₂₎과 00100₍₂₎을 AND 연산하면, 결과는 0이 나옵니다. 즉, false(방문하지 않음)입니다. 

  10010
& 00100
---------
  00000

예를 들어 visited가 10010₍₂₎이고, nx가 1이라면, (1 << nx)는 00010₍₂₎이 됩니다.

10010₍₂₎과 00010₍₂₎을 AND 연산하면, 결과는 2이 나옵니다. 즉, true(이미 방문함)입니다. 

  10010
& 00010
---------
  00010

 

또한, (visited | 1 << nx)로 nx를 방문 표시할 수 있습니다.

예를 들어, visited가 10010₍₂₎이고, nx가 2일 때, (visited | 1 << nx)의 결과는 10110₍₂₎입니다.

  10010
| 00100
---------
  10110

 

🚀 Solution 

---

아래는 전체 코드입니다.

// Created by 길민호 on 2022/07/02.

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define x first
#define y second
#define SIZE 12
#define INF 100000
int weight[SIZE][SIZE];
int d[SIZE][1<<SIZE];  // d[cur][visted]는 현재 cur이고, visted를 방문한 상태일 때, 고객들을 모두 방문하고, 집으로 돌아가는 최소 비용
int n;
pii st, en; // 회사, 집의 위치

int TSP(int cur, int visited){
    int &ret = d[cur][visited];
    if(ret != 0) return ret;

    if(visited == (1 << (n + 1))-1) {    // 모두 방문한 경우
        return weight[cur][n + 1];
    }

    ret = INF;
    for(int i = 0; i <= n; i++){
        if(visited&(1<<i)) continue; // 이미 방문한 경우
        // 방문하지 않은 경우
        ret = min(ret, TSP(i, (visited|1<<i)) + weight[cur][i]);
    }
    return ret;
}

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

    int t; cin >> t;
    int cur = 1;
    while(t--){
        vector<pii> pos;
        fill(&d[0][0], &d[SIZE - 1][1 << SIZE], 0);

        cin >> n;
        cin >> st.x >> st.y;
        cin >> en.x >> en.y;

        pos.push_back(st);
        for(int i = 0; i < n; i++){
            pii c; cin >> c.x >> c.y;
            pos.push_back(c);
        }
        pos.push_back(en);

        for(int i = 0; i < n + 2; i++)
            for(int j = 0; j < n + 2; j++)
                weight[i][j] = abs(pos[i].x - pos[j].x) + abs(pos[i].y - pos[j].y);

        int shortest = TSP(0, 1);
        cout << "#" << cur++ << " " << shortest << "\n";
    }
}