[백준 11403] 경로 찾기

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

11403번: 경로 찾기

 

 

문제

가중치 없는 방향 그래프 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

 

---

노드의 개수가 100 으로 작은 편이기 때문에 플로이드 워셜 알고리즘을 이용하여 경로를 탐색하는 것이 편하다.

 

기존의 플로이드 워셜 알고리즘은 최단 거리를 구하는 것으로,

 

A-B 까지 최단 경로가 있다고 하고, 그 사이에 노드 K 가 있다면 A-K, K-B 또한 부분 최단 경로가 된다는 것을 이용하여 모든 노드 간 최단 거리를 구할 수 있다.

 

이를 조금만 수정하자.

 

A-B 사이에 중간 노드 K 가 연결되어 있다면, A-B 또한 연결된 것이다.

 

즉, graph[a][k] == 1 이고 graph[k][b] == 1 이면 graph[a][b] == 1 일 것이다.

 

이를 이용하여 구현하자.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int graph[][];

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine()); // 노드 개수

        graph = new int[n + 1][n + 1];

        // 초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    graph[i][j] = 0;
                else
                    graph[i][j] = 10000000;
            }
        }

        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine());
            for(int j = 1 ; j <= n ; j ++){
                int cost = Integer.parseInt(stk.nextToken());
                if(graph[i][j] > cost && cost != 0){
                    graph[i][j] = cost;
                }
            }
        }
        // 플로이드 - 워셜 알고리즘 O(v^3)
        for (int k = 1; k <= n; k++) {
            for (int s = 1; s <= n; s++) {
                for (int e = 1; e <= n; e++) {
                    if (graph[s][k] == 1 && graph[k][e] == 1)
                        graph[s][e] = 1;
                }
            }
        }

        // 정답 출력
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] == 10000000)
                    bw.write("0 ");
                else
                    bw.write(graph[i][j] + " ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
}