[C++] 백준 1976번: 여행 가자 (플로이드 워셜)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

주어진 도시의 연결 상태에 대해 입력 받은 순서대로 모든 도시를 방문할 수 있는지 여부를 구하여라.

---

시간복잡도 어림하기

플로이드 워셜(Floyd - Warshall) 알고리즘

 문제를 해결하기 위해 모든 도시에 대한 거리 정보가 필요하므로 플로이드 워셜 알고리즘을 사용할 수 있습니다. 프로이드 워셜 알고리즘의 시간복잡도는 O(n^3)이고, 문제에서 n의 최댓값은 200 이므로 200^3 = 8,000,000입니다. 따라서 제한 시간 내에 문제를 해결하기 적절한 알고리즘입니다.

---

알고리즘 설계하기

 이번 문제는 입력으로 들어온 도시 순서대로 방문할 수 있는지 확인하는 문제입니다. 따라서 어떤 도시에 대해 각 도시로 이동하는 최단 거리 정보가 필요합니다. 이는 플로이드 워셜 알고리즘을 통해 구할 수 있습니다.  

 

플로이드 워셜 알고리즘은 다음과 같이 for 루프 세 개를 중첩하여 구현합니다.

for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            /*i노드에서 j노드까지 최단거리는 i에서 j까지의 최단거리와*/
            /*i노드에서 k노드를 경유하여 j까지 가는 최단거리의 최솟값*/
        }
    }
}

 

 이렇게 모든 도시에 대해 모든 도시로 이동하는 최단거리를 구했다면, 다음으로 입력 받을 순서대로 도시에 방문할 수 있는지를 구해야합니다.

 

 이는 for 루프를 돌면서 이전 도시에서 현재 도시까지 경로가 존재하는지 여부만 확인하는 방식으로 구현할 수 있습니다. 코드로는 다음과 같이 구현할 수 있습니다.

int cur = 첫 방문 노드;
for(int i = 1; i < m; i++){
    if(cur에서 i번째 도시로 방문하는 경로가 존재하지 않는 경우){
        flag = 0;// 실패 flag
        break;
    }
}

---

알고리즘 구현하기

#include<iostream>
#include<vector>
#define INF 1e9
using namespace std;

int n, m, adj[204][204];
vector<int> v;
int main(){
    cin >> n >> m;
    int num;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> num;
            if(num == 0) adj[i][j] = INF; //경로가 존재하지 않는 경우
            else adj[i][j] = 1;
            if(i == j) adj[i][j] = 1; //자기 자신으로 이동하는 경우
        }
    }
    for(int i = 0; i < m; i++){
        cin >> num;
        v.push_back(--num); //도시 번호는 1번부터 시작하므로 0번부터 시작하기 위해 1줄임
    }

    /*플로이드 워셜 알고리즘*/
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    /*경로 존재 탐색*/
    int cur = v[0], flag = 1;
    for(int i = 1; i < m; i++){
        int next = v[i];
        if(adj[cur][next] == INF){ //cur부터 next까지 경로가 존재하지 않음
            flag = 0; break;
        }
        cur = next;
    }
    cout << (flag == 1 ? "YES" : "NO");
    return 0;
}

 위 코드는 입력을 받으면서 adj 배열을 초기화 하고, 플로이드 워셜 알고리즘을 통해 모든 최단 경로를 구한 뒤 도시 방문이 가능한지 여부를 확인하는 코드입니다.

 핵심 로직인 프로이드 워셜 알고리즘과 도시 방문이 가능한지 확인하는 로직은 설계 단계에서 확인한 것과 동일합니다.

 

 위 코드에서 주의해야 할 점은 도시 번호가 1번부터 시작하기 때문에 방문할 도시 순서를 입력받는 부분에서는 도시 번호를 1 줄여주어야 합니다.

 또한, 입력으로 이동 불가한 도시 경로는 0으로 들어오는데, 자기 자신으로 이동하는 경우도 0으로 들어오므로 예외 처리가 필요합니다. 때문에, 자기 자신으로 이동하는 경우에는 경로가 존재한다는 1로 따로 처리했습니다.

---