백준 17182번 : 우주 탐사선(골드 3)

문제

모든 행성을 방문하되 최소 비용을 구하는 문제이다

특이한 점으로는 방문한 행성을 다시 방문할 수 있다

풀이

이번 문제는 조금 이해가 어려웠다. 평소대로 최단 경로를 다익스트라로 구하려 했지만 같은 행성을 방문할 수 있다는 조건이 있었기 때문이다

왜 같은 행성을 방문해도 된다는 조건이 붙었냐면 예제 입력 2를 보면

4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

여기서 모든 행성을 방문하는 최단 경로는 1(시작) -> 0 -> 3 -> 0 -> 2의 74 시간이다

3번 행성에서 2번 행성으로 가는 것보다 3번 행성에서 0번 행성을 방문하고 0번 행성에서 2번 행성으로 가는 비용이 더 적다

그러므로 여기서 선택할 수 있는 알고리즘이 플로이드-워셜이다. i번에서 j번으로 가는 최단 경로를 구할 수 있는 시간 복잡도가 큰 알고리즘이다. 여기선 N이 10까지이므로 충분하다

시간을 입력 받은 배열을 각 행성에서 다른 행성으로 최단 경로로 업데이트 한 다음 DFS를 통해 방문하지 않은 행성을 탐색하며 모든 행성을 탐색했다면 정답을 업데이트한다

여기서 visit 배열을 쓸 수 있겠지만 N이 10이하이므로 방문을 비트마스킹으로 처리했다

백트래킹으로 방문이 끝났으면 방문 처리를 되돌리는 작업도 해줘야 함

코드

#include <bits/stdc++.h>
using namespace std;

int N, K;
int T[11][11];
int answer = INT_MAX;

void Input()
{
    cin >> N >> K;

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

void DFS(int here, int time, int visit)
{
    if (visit == (1 << N) - 1)
    {
        answer = min(answer, time);
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (visit & (1 << i)) continue;

        DFS(i, time + T[here][i], visit | (1 << i));
    }
}

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

    DFS(K, 0, 1 << K);

    cout << answer;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Input();

    Solve();

    return 0;
}

회고

처음에는 플로이드 워셜로 최단 경로를 구했지만 문제 조건에 맞지 않게 DFS에서 왜 방문한 배열을 다시 방문하지 않지??라고 생각했는데 좀 바보같았다

플로이드 워셜로 이미 업데이트해서 최단 경로로 모든 행성을 방문하는 것만 하면 됐는데..