백준 17182 - 우주 탐사선

문제 설명

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

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

---

 

 

 

 

 

 

제한 사항

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)

다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 행성끼리의 거리가 주어질 때 하나의 행성에서 출발하여 모든 행성을 탐험하는 최소 비용을 구해야 한다.

처음에는 다익스트라를 통해 각 행성까지의 최단 거리를 구하면 된다고 생각했다.

하지만, 각 노드까지의 최단거리가 아니라 모든 행성을 특정 순서로 방문하며 거리가 누적되기 때문에 여러가지의 경우의 수가 생긴다.

따라서, 모든 노드끼리의 최단 거리를 구한 뒤, dfs를 통해 최단거리를 체크해야 한다.

 

모든 노드끼리의 최단 거리를 구하기 위해서는 플루이드 와샬 알고리즘을 사용하면 된다.

플루이드 와샬은 임의의 한 노드를 중간으로 설정하고 해당 노드를 거쳐 다른 노드로 이동하는 거리를 비교하며 최단 거리를 구하는 알고리즘이다.

    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (Planets[i][j] > Planets[i][k] + Planets[k][j])
                {
                    Planets[i][j] = Planets[i][k] + Planets[k][j];
                }
            }
        }
    }

이후, dfs를 통해 최단 거리를 구하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int ans = INT_MAX;
bool visited[10] = { false, };

void dfs(int start, int dist, int depth, vector<vector<int>>& Planets) 
{
    if (ans < dist) return;
    
    if (depth == Planets.size()) {
        ans = min(ans, dist);
        return;
    }

    for (int i = 0; i < Planets.size(); i++) {
        if (visited[i]) continue;
        visited[i] = true;

        dfs(i, dist + Planets[start][i], depth + 1, Planets);
        visited[i] = false;
    }
}

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

    int N, S;
    cin >> N >> S;

    vector<vector<int>> Planets(N, vector<int>(N));

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

    for (int k = 0; k < N; k++)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (Planets[i][j] > Planets[i][k] + Planets[k][j])
                {
                    Planets[i][j] = Planets[i][k] + Planets[k][j];
                }
            }
        }
    }

    dfs(S, 0, 0, Planets);
    cout << ans;

    return 0;
}

---