백준 11403: 경로 찾기

경로 찾기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

31823

18181

13097

56.621%

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1 복사

3
0 1 0
0 0 1
1 0 0

예제 출력 1 복사

1 1 1
1 1 1
1 1 1

예제 입력 2 복사

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력 2 복사

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: degurii

dfs로도 풀 수 있지만 푸는 방식이 워셜이랑 비슷해서 워셜 알고리즘을 찾아봤따. 

#include <iostream>
#include <algorithm>
using namespace std;

#define INF 987654321
int arr[101][101];
int n;

int main() {

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0)
                arr[i][j] = INF;
        }
    }

    /*for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }*/
    for (int bridge = 1; bridge <= n; bridge++) {
        for (int from = 1; from <= n; from++) {
            for (int to = 1; to <= n; to++) {
                arr[from][to] = min(arr[from][to], arr[from][bridge] + arr[bridge][to]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == INF)
                cout << 0 << ' ';
            else
                cout << 1 << ' ';
        }
        cout << '\n';
    }


    return 0;
} 

코드는 이렇게되는데 

    for (int bridge = 1; bridge <= n; bridge++) {
        for (int from = 1; from <= n; from++) {
            for (int to = 1; to <= n; to++) {
                arr[from][to] = min(arr[from][to], arr[from][bridge] + arr[bridge][to]);
            }
        }
    }

 

이게 워셜 알고리즘의 핵심이다. 

처음 설정하는 bridge는 말 그대로 브릿지다. 얘를 통해서 가는 것이 빠른지, 아니면 바로 가는게 빠른지를 비교한다.

우리는 앞서 arr[i][j]==0이면 987654321 (INF)라는 큰 값을 넣어줬다. 그러면 워셜을 돌면서 INF값이 min함수에 의해 갱신되고 값이 있는것은 1로 INF는 0으로해서 다시 출력해주면 된다. 

워셜은 시간복잡도가 크기때문에 함부로 사용할 수 없다.