[Java] baekjoon_11403 : 경로 찾기

그래프 이론, 그래프 탐색, 최단 경로, 플로이드–워셜

경로 찾기 : Silver1

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

 

플로이드 와샬

플로이드 와샬 알고리즘에 대해 알지 못하는 상태라 먼저 해당 알고리즘에 대해 학습해보았다.

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

플로이드-와샬 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다.

여기서는 경로의 존재 여부를 확인하는 데 사용했다.

 

문제 이해

입력

• 첫 줄에 정점의 개수 N (1 ≤ N ≤ 100)
• 다음 N개의 줄에 걸쳐 N×N 크기의 인접 행렬이 주어진다.
  • 행렬의 원소 값이 1이면 i에서 j로 가는 간선이 존재.
  • 행렬의 원소 값이 0이면 i에서 j로 가는 간선이 존재하지 않음.
  • i에서 i로 가는 경로는 항상 0으로 주어집니다.

출력

주어진 그래프에서 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로가 존재하면 1, 그렇지 않으면 0을 인접 행렬 형식으로 출력한다.

 

 

풀이 방법

초기화

주어진 인접 행렬을 초기화한다.

 

중간 정점을 통해 경로를 갱신

각 정점을 중간 정점으로 사용하여 경로를 갱신한다.

=> i에서 j로 직접 가는 경로가 없더라도, i에서 k를 거쳐 j로 가는 경로가 있을 수 있다. 이 과정을 반복하여 모든 경로 정보를 갱신한다.

 

풀이

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());
        int[][] graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 플로이드-와샬 알고리즘 적용
        for (int k = 0; k < N; k++) { // 거쳐가는 정점
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (graph[i][k] == 1 && graph[k][j] == 1)
                        graph[i][j] = 1;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bw.write(graph[i][j] + " ");
            }
            bw.newLine();
        }
        bw.flush();
        br.close();
        bw.close();
    }
}

 

 

입력을 아래와 같이 예를 들자면,

3
0 1 0
0 0 1
1 0 0

 

정점 0에서 정점 1로 가는 경로가 존재함

정점 1에서 정점 2로 가는 경로가 존재함

정점 2에서 정점 0으로 가는 경로가 존재함

 

거쳐가는 정점인 k = 0인 경우,

graph[2][0] == 1 && graph[0][1] == 1 이면, graph[2][1] = 1로 만들어준다. => 2에서 0을 거쳐서 1로 갈 수 있다.

 

거쳐가는 정점인 k = 1인 경우,

graph[0][1] == 1 && graph[1][2] == 1 이면, graph[0][2] = 1로 만들어준다. => 0에서 1를 거쳐서 2로 갈 수 있다.

 

거쳐가는 정점인 k = 2인 경우,

graph[1][2] == 1 && graph[2][0] == 1 이면, graph[1][0] = 1로 만들어준다. => 1에서 2를 거쳐서 0로 갈 수 있다.

 

그러므로,

최종 행렬의 형태는

1 1 1
1 1 1
1 1 1

이렇게 된다.