[백준 17182] 우주 탐사선

처음에는 최단경로 + 모든 행성 탐사라고 해서 크루스칼 MST를 생각했지만

아래와 같은 생각으로 MST는 아닌 것을 알았다.

 

1. 방향 그래프

→ MST면 2차원 배열로 그래프 표현하지 않아도 되는데 이 문제는 굳이 2차원 배열로 각 경로들간 값을 주고 있다.

→ 그리고 방향그래프면 크루스칼로 못푼다

 

2. 탐사선이 발사되는 행성을 준다

→ ㄹㅇ 개뜬금없는 조건이라 생각했는데 오히려 이 조건을 무조건 사용해야한다.

 

먼저 방향그래프이고 "이미 방문한 행성도 중복해서 갈 수 있다" 이런 얘기가 있어서

우선 가장 먼저 브루트포스 방법으로 재귀넣고 돌리는 방법을 생각했다.

아주 무식하게 돌리다 방문여부가 다 1이되면 끝내는 방식으로 말이다.

근데 그러면 무한루프 돌게된다.

 

따라서 플로이드워셜로 미리 N에서 M 정점까지의 최소값을 구해놓은뒤,

아직 방문안한 다음 정점 + 경로값을 인자로 넣어 재귀돌릴 수 있게 했다.

 

N이 10인 이유가 dfs로 정점 방문 순서에 대한 조합을 따져보면 10!인데 10! < 1초 안에 무조건 해결되기 때문이다.

그리고 탐사선 발사되는 행성을 준 이유가 이 재귀에 시작점을 K로 두고 하라는 얘기이다.

따라서 사실 10!이 아니라 9!이다.

K 맨 처음에 놓고 나머지 9개에 대한 조합이므로

 

즉 그래프이론(플로이드워셜) + 조합론(DFS/BFS) 문제이다.

---

#include <iostream>
#include <vector>
#include <bitset>

#define SIZE 10
#define INF int(1e9)

using namespace std;

int N, K;
int map[SIZE][SIZE];
int ans = INF;

// 모든 행성을 탐사해야함
// 최소시간
// 방향그래프

// 조합으로 돌려보기
// 10!이라 1초 안에 가능함
void dfs(int cur, int cost, bitset<SIZE> visited)
{
    // 종료가능하면 종료
    if (visited.count() == N)
    {
        if (cost < ans)
        {
            ans = cost;
        }
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = 1;
            dfs(i, cost + map[cur][i], visited);
            visited[i] = 0;
        }
    }
}

// 플로이드워셜로 돌려보기
void solve()
{
    for (int mid = 0; mid < N; mid++)
    {
        for (int start = 0; start < N; start++)
        {
            for (int end = 0; end < N; end++)
            {
                map[start][end] = min(map[start][end], map[start][mid] + map[mid][end]);
            }
        }
    }

    // K에서 시작
    bitset<SIZE> visited;
    visited[K] = 1;
    dfs(K, 0, visited);
}

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

    cin >> N >> K;

    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            cin >> map[i][k];
        }
    }

    solve();

    cout << ans;

    return 0;
}