[Algorithm] 백준 17182 우주 탐사선 - C++, 플로이드 와샬

17182번: 우주 탐사선

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int NODE = 11;
const int MAX = 999999999;

int costs[NODE][NODE];
bool visit[NODE];
int planetNumber, StartPlanet;
int answer = MAX;

void Launch(int curPos, int visitCount, int curCost){
    if(curCost > answer)    return;

    if(visitCount == planetNumber-1){
        answer = min(answer, curCost);
        return;
    }

    for(int i = 0; i < planetNumber; i++){
        if(!visit[i]){
            visit[i] = true;
            Launch(i, visitCount + 1, curCost + costs[curPos][i]);
            visit[i] = false;
        }
    }
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(visit, false, sizeof(visit));
    
    // input;
    cin >> planetNumber >> StartPlanet;
    for(int i = 0; i < planetNumber; i++){
        for(int j = 0; j < planetNumber; j++){
            cin >> costs[i][j];
        }
    }

    // floyid
    for(int via = 0; via < planetNumber; via++){
        for(int from = 0; from < planetNumber; from++){
            for(int to = 0; to < planetNumber; to++){
                if(costs[from][to] > costs[from][via] + costs[via][to])
                    costs[from][to] = costs[from][via] + costs[via][to];
            }
        }
    }

    // Search
    visit[StartPlanet] = true;
    Launch(StartPlanet, 0, 0);

    cout << answer << '\n';
}

---

 행성 수가 10개밖에 안되고 입력이 딱봐도 플로이드 와샬을 쓰라고 알려줬습니다. 처음엔 입력이 무슨 의미인줄 몰랐으나 그냥 플로이드 와샬을 하기 전 각 행성간 거리를 주는 것이었습니다. 모든 정보를 다 주니 memset도 할 필요가 없었습니다.

 

 플로이드 와샬로 각 행성들간 거리를 다 구했다고 하면 이후 DFS를 통해서 최솟값을 찾으면 됩니다.

---

 추가로 보면 이 문제는 입력값을 잘만 처리해주면 다익스트라로 풀 수 있는 문제기도 하지만 그러면 플로이드 와샬보다 복잡해질 것 같아 따로 풀이하지는 않았습니다.