[Java] 그래프 탐색, 플로이드–워셜 | 백준 11403 경로찾기

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

 

백준 11403번 : 경로 찾기

접근 방식 

 

우선 정점 i에서 j로 가는 길이가 양수인 경로의 의미를 이해하려 해보았다.

그래프 G에서 정점 (i,j)는  i에서 j로 가는 간선의 유무를 나타낸다.

그래프 G의 정점(i,j)는 노드 i에서 노드 j로 직접 연결된 간선이 있어야 1이 되는 반면, 

정점 i에서 j로 가는 길이가 양수인 경로는 노드 i에서 1개 이상의 간선을 거쳐 노드 j로 도달할 수 있는지에 주목한다.

노드 1과 노드 2 사이에 직접 연결된 간선이 없어도 노드 1 => (노드 x1 => ... => 노드 xn) => 노드 2 와 같이 연결될 수 있다면 

(노드 1, 노드 2)은 1인 경우가 된다.

 

기본적으로 그래프 G에서 1인 G[i][j]는 우리가 구하고자하는 인접행렬에서도 1이 되므로, 추가적인 배열없이 그래프 G를 업데이트하며 최종 답을 구할 수 있을 것이라 판단했다.

 

우선 그래프 G를 순회하며 1일때를 확인해야 하므로 기본적으로 이중 for문이 필요할 것이다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if(i -> j 연결되는지){
            G[i][j] = 1;
        }
    }
}

 

i에서 j 1개 이상의 간선을 거쳐 연결이 되는지를 판단할 조건이 필요하다. 

노드 1 => (노드 x1 => ... => 노드 xn) => 노드 2  인 상황이 성립하려면

우선 노드 1 => (노드 x1 => ... => 노드 xn), (노드1, 노드 xn)이 1이 되어야하고,

(노드 x1 => ... => 노드 xn) => 노드 2 , (노드 x1, 노드 2) 또한 1이 되어야한다.

따라서, 임의의 노드 n을 거쳐 i에서 j로 연결되는지 확인하기위해 G[i][n] == 1 && G[n][j] == 0 임을 확인하면 될 것이다.

 

각 노드를 차례로 거처가는 노드로 선정한 후 그래프G에 대해 이중 for문을 돌려주면 최종적으로 정점 i에서 j로 가는 길이가 양수인 경로가 1인 결과를 얻을 수 있다.

for(int n=0; n < N; n++) { //거처가는 노드 n
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(G[i][n] == 1 && G[n][j] == 1){//i->n && n->j => i->j
                G[i][j] = 1;
            }
        }
    }
}

 

이때 거처가는 노드 n은 꼭 0부터 N-1순으로 확인하지 않아도 결과는 동일하다. (각 경로는 다른 경로의 발견 여부와 관계없이 독립적이고, 이중 for문이 매번 업데이트된 모든 노드 쌍 (i,j)에 대해 i->n->j를 계산하기 때문이다)

 

최종 코드 

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int N = Integer.parseInt(br.readLine());
        G = new int[N][N];
        //그래프 인접행렬
        for(int i=0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j < N; j++){
                G[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int n=0; n < N; n++) { //거처가는 노드 n
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(G[i][n] == 1 && G[n][j] == 1){//i->n && n->j => i->j
                        G[i][j] = 1;
                    }
                }
            }
        }

        for(int[] g : G){
            for(int r : g){
                System.out.print(r+" ");
            }
            System.out.println();
        }
    }
}

 

3중 for문을 사용했기 때문에 시간 복잡도 : O(n^3)

 

최적화를 시키기 위해 아래와 같이 i->n이 1이 아니면  j 루프를 돌지 않게 수정해보았는데 큰 차이는 없었다. 

for(int n=0; n < N; n++) { //거처가는 노드 n
    for (int i = 0; i < N; i++) {
        if(G[i][n] == 1) { //i->n 이 1이 아니면 skip
            for (int j = 0; j < N; j++) {
                if (G[i][j] == 0 && G[n][j] == 1) {// i->j 이 이미 1이면 skip, n->j이 1이면 i->j 는 1
                    G[i][j] = 1;
                }
            }
        }
    }
}

 

출력 부분을 StringBuilder를 사용하여 출력을 모아서 한 번에 처리하는 방식으로 수정해보니 메모리와 시간을 크게 단축할 수 있다는 것을 확인했다. System.out 은 I/O 작업이기 때문에 StringBuilder를 사용하여 최대한 IO 작업을 줄이고, String 문자열 결합을 줄여 메모리 절약도 가능하다. (메모리 : 20076KB -> 15996KB, 시간 : 316ms -> 152ms)

StringBuilder sb = new StringBuilder();
for(int[] g : G){
    for(int r : g){
        sb.append(r).append(" ");
    }
    sb.append("\n");
}
System.out.print(sb);

 

느낀 점

앞으로 StringBuilder 사용에 더 익숙해지도록 노력해야겠다!