BOJ 17182 - 우주 탐사선

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

 

플로이드워셜 + 완전탐색 백트래킹으로 풀었다. 재밌는 문제였다.

 

처음에는 문제를 보자마자 N도 작고 해서 아 이거 플로이드 워셜이구나 생각했다.

그래서 각 정점에서 다른 정점으로 가는 최소값을 구하고, 이제 한 정점에서 다른 정점으로 가는 최솟값들을 더해주면 된다고 생각했다.

(0에서 1,2,3 번으로 가는 최소값을 보고 가장 최소인 값으로 이동하고, 또 그점에서 다른 정점으로 가는 최솟값들을 보고... 이런식으로 일종의 그리디처럼)

그런데 하면서 든 생각이 그리디처럼 어느 한 정점에서 다른 정점으로 가는 최솟값들을 모두 더한 값이 전체의 최소값은 아닐 수 있다는 생각이 들었다.

그래서 아 완전탐색이구나 라는 생각이 들어 완전탐색으로 풀었다.

그런데 예제 2번에서 통과를 못하는 거다.

이거 왜이러지 싶어서 고민하고, 문제도 다시보고 했는데, 이미 반복한 행성도 중복으로 갈수있다라는 말이 있었다.

아 그러면 최소값으로 모든 정점을 방문하기만 하면 되는구나.

그래서 플로이드 워셜로 구한 한 정점에서 다른 정점으로 가는 최소값 + 완전탐색으로 모든 정점을 탐색하면서 그중 최소값을 구해줬다.

재밌는 문제였다.

#include <bits/stdc++.h>
using namespace std;
int a[14][14];
int visited[14];
int m[14][14];
int n;
int k;
int inf = 1e9;
int mn = inf;

void go(int v, int cnt, int sum)
{
    // cout << "v : " << v << ", cnt : " << cnt << ", sum : " << sum << "\n";
    if (sum >= mn)
    {
        return;
    }
    if (cnt == n)
    {
        mn = min(mn, sum);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (visited[i])
        {
            continue;
        }

        visited[i] = 1;
        go(i, cnt + 1, sum + m[v][i]);
        visited[i] = 0;
    }
}

int main()
{
    cin >> n >> k;

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

    fill(&m[0][0], &m[0][0] + 14 * 14, inf);
    for (int i = 0; i < n; i++)
    {
        m[i][i] = 0;
    }

    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (m[i][j] > a[i][k] + a[k][j])
                {
                    m[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }

    visited[k] = 1;
    go(k, 1, 0);
    cout << mn << "\n";

    return 0;
}