[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선

다익스트라, 다이나믹 프로그래밍, 비트마스킹

---

 

[백준 13308] 주유소 (C++)

얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다

 

모든 행성이 서로 이어져 있고, 모든 행성을 방문해야하며, 행성을 중복해서 방문할 수 있다고 주어졌다.

 

행성을 중복해서 방문할 수 있다는 점과 N이 최대 10인 점을 보니 예전에 풀었던 비트필드를 통해서 방문여부를 체크해주는 외판원 문제가 생각이났다.

 

이 문제도 마찬가지로 2차원 dp배열을 사용하면서 방문기록이 같은데 이미 방문한 정점을 다시 방문하는 경우 건너뛰는 방법을 사용해서 중복탐색을 없앴다.

dp[현재행성][방문기록] = -1이 아닌 값 아무거나

 

다익스트라 알고리즘을 베이스로 최단거리를 탐색하고 비트마스킹을 통해서 방문여부를 체크해주면된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct P{
    int planet;
    int visited;
    int cost;
};
 
struct cmp{
    bool operator()(P &a, P &b){
        return a.cost > b.cost;
    }
};
 
int N, K, check;
int Cost[11][11];
// 현재 정점, 지금까지 지나온 경로
int dp[11][1 << 10];
 
void input(){
    cin >> N >> K;
    int a;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Cost[i][j];
        }
    }
    check = (1 << N) - 1;
    memset(dp, -1, sizeof(dp));
}
 
void solve(){
    priority_queue<P, vector<P>, cmp> pq;
    pq.push({K, (1 << K), 0});
    
    
    while(!pq.empty()){
        int now = pq.top().planet;
        int now_cost = pq.top().cost;
        int visit = pq.top().visited;
        pq.pop();
        
        if(dp[now][visit] != -1) continue;
        dp[now][visit] = now_cost;
        
        if(visit == check){
            cout << now_cost << "\n";
            return;
        }
        
        for(int next = 0; next < N; next++){
            if(next == now) continue;
            int next_cost = now_cost + Cost[now][next];
            int visited = visit | (1 << next);
            
            if(dp[next][visited] != -1) continue;
            pq.push({next, visited, next_cost});
        }
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}