[백준/C++] 11403번: 경로 찾기

문제

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

---

문제 요약

가중치가 없는 방향 그래프 G에 대한 정보가 인접 행렬로 주어진다.

 

이 때, 모든 정점 (i, j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 없는지를 출력한다.

 

+ 있으면 1, 없으면 0을 출력한다.

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;

// res[i][j]: i에서 j로 갈 수 있는지 정보 (1 or 0)
int res[1010][1010];

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    // 단일 간선을 통해 i에서 j로 갈 수 있는지에 대한 정보 입력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> res[i][j];
        }
    }

    // i에서 k를 거쳐 j로 갈 수 있는지 탐색
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (res[i][k] + res[k][j] == 2) {
                    res[i][j] = 1;
                }
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << res[i][j] << " ";
        }
        cout << "\n";
    }
}

---

코드 설명

플로이드 워셜 알고리즘을 통해 문제를 해결한다.

 

1. i에서 j로 갈 수 있는지에 대한 정보를 res배열에 저장한다.

+ 갈 수 있으면 1, 없으면 0으로 저장한다.

 

2. 3중 반복문을 통해 i에서 k를 거쳐 j로 갈 수 있는지를 탐색한다.

 

3. res 배열을 탐색한다.

---

고찰

플로이드 알고리즘을 이용할 때, 가장 주의해야할 점은 3중 반복문을 k, i, j 순서로 작성해야 한다는 것이다.

 

i, j, k 순서로 진행할 경우, 아직 갱신되지 않은 정보에 대해 접근하여 갱신이 이루어지게 된다.