[Algorithm]Baekjoon 17182번 :: 우주 탐사선

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

17182번: 우주 탐사선

int n, k;
int adjMatrix[11][11];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> k;
 
    vector<int> v;
 
    for (int i = 0; i < n; ++i)
    {
        v.push_back(i);
    }
 
 
    memset(adjMatrix, 0x3f, sizeof(adjMatrix));
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> adjMatrix[i][j];
        }
    }
 
    for (int k = 0; k < n; ++k)
    {
        for (int i = 0; i < n; ++i)
        {
            if (adjMatrix[i][k] != 0x3f3f3f3f)
            {
                for (int j = 0; j < n; ++j)
                {
                    if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j])
                    {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                    }
                }
            }
        }
    }
 
    int answer = 0x3f3f3f3f;
 
    do
    {
        if (v[0] != k) continue;
 
        int sum = 0;
 
        for (int i = 1; i < v.size(); ++i)
        {
            sum += adjMatrix[v[i - 1]][v[i]];
        }
 
        answer = min(answer, sum);
 
    } while (next_permutation(v.begin(), v.end()));
 
    cout << answer;
 
    return 0;
}

 

플로이드와샬을 이용해 각 노드간의 최단거리를 먼저 구했고, 그 후에 출발위치를 기점으로 방문할 수 있는 모든 경우의 수를 이용해서 최솟값을 구하였다.

 

모든 경우의 수를 구하는 것에는 next_permutation을 사용했다. 사실 이전까지는 DFS로 가짓수 뽑아서 하기도 했는데, 사용법이 너무 편리해서 나도 이제 next_permutation을 사용할 것 같다.