[BOJ / C++] 우주 탐사선 (골드3 - 플로이드, 백트래킹, 람다함수)

문제링크: https://www.acmicpc.net/problem/17182

 

1. 코드

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

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

    int n, k;
    cin >> n >> k;

    vector<vector<int>> d(n+1, vector<int>(n+1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> d[i][j];
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    
    int minTime = INT_MAX;
    vector<bool> vis(n, false);
    vis[k] = true;


    function<void(int, int, int)> dfs = [&](int cur, int cost, int cnt) {
        if (cnt == n) {
            minTime = min(minTime, cost);
            return;
        }

        for (int nxt = 0; nxt < n; nxt++) {
            if (!vis[nxt]) {
                vis[nxt] = true;
                dfs(nxt, cost + d[cur][nxt], cnt+1);
                vis[nxt] = false;
            }
        }
    };

    dfs(k, 0, 1);

    cout << minTime;

}

 

 

2. 시간복잡도

• 플로이드에 걸리는 시간복잡도은 O(n^3)이다.
• 백트래킹에 걸리는 시간복잡도는 아래와 같다.
  (전체 재귀 호출 횟수) * (한 번 호출될 때 내부에서 도는 루프 횟수) = O((n-1)! * n) = O(n!)
• n = 10이고, 10^3 = 1000, 10! = 3,628,800 < 10^8 이므로 시간 내에 통과 가능하다.

 

3. 분석

• TC1을 인접행렬과 그래프 형식으로 나타내면 위와 같다.
• 이 문제에서 문제 조건 중 " 탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다."라는 조건이 있다.
• 중복해서 갈 수 있다는 말은 플로이드를 이용해 d 테이블을 갱신해도 된다는 말이다.
• 이렇게 각각에 도달하는 최소시간의 d 테이블을 만들어놓고 dfs 백트래킹을 통해 모든 경우의 수 중 가장 적은 시간이 소요되는 경우를 고르면 된다. 즉 백트래킹은 방문 순서만을 결정하는 것이다.
• 플로이드로 최소 시간으로 갱신해놓지 않으면 백트래킹을 언제 멈춰야할지 알 수가 없다. (백트래킹은 순서를 결정할 뿐이다.)
• 즉, 플로이드로 최소 시간 테이블 구현 + 백트래킹으로 방문 순서 결정의 아이디어로 푸는 문제였다.

 

 

* 프로그래머스의 파라미터로 입력값을 전달하는 스타일 때문에 전역변수 선언이 어렵고, 일일이 참조자 전달을 하기에 파라미터가 너무 더러워져서 람다함수 방식을 써봤다. 익숙해지면 람다함수 방식이 백트래킹, dfs, 재귀 형식의 코드에서 더 깔끔할 것 같다.