[Java] 백준 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으로 출력해야 한다.

 

[예제 입력]

 

[풀이과정]

처음 풀이는 ArrayList 배열을 만들어서 출발노드와 도착노드의 관계성을 구현해보았다. <예제 입력1>로 설명해보자면 다음 그림과 같다.

 

1)   arrayLists[시작점].size()만큼 반복하며 시작점과 연결관계가 있는 노드를 arrayList[시작점].get(i)를 해서 넘어갈 노드의 값을 가져온다.

2) 이때 넘어갈 노드의 값을 가지고 재귀 연산을 하여 타고타고 들어가서 방문한 노드는 체크(true)해준다.

3) visit[도착해야하는 노드]  = true이면 경로가 있는 것이므로 "1을"출력하고 아니라면 "0"을 출력해주면된다.

 

 

이렇게 풀었더니 304ms 시간이 걸렸다. 다른 사람들이 풀이를 보니 약 180ms시간이 걸린 코드가있었다. 내가 푼 코드와 달리 시간 단축이 되어 있어서 코드를 비교하기로 하였다.

 

---

다른 코드를 보니 <플로이드 - 와샬>  알고리즘을 바탕으로 문제를 풀었다. 플로이드 - 와샬에 대한 설명을 해놓은 블로그 글이 있어 이 글을 읽고 알고리즘에 대해서 이해하게 되었다. (https://blog.naver.com/ndb796/221234427842)

 

플로이드 - 와샬은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 쓰는 알고리즘이다. 이 문제에서는 최단 경로를 구하진 않는다. 하지만 이 알고리즘을 이용한다면 모든 정점에서 모든 정점으로의 경로가 존재하는지 않하는지 알 수 있다. 이 점을 가지고 코드를 작성하였다.  시간 복잡도는 O(n^3)을 가지지만 이 문제에서 N의 최대값이 100 이기 때문에 

그렇게 오래 걸리지 않는다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

//경로찾기
public class Main {
    static ArrayList<Integer> arrayLists[];
    static boolean visit [] ; // 방문 체크
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine()); //2차원 배열 크기
        visit = new boolean[N];
        arrayLists = new ArrayList[N];

        for (int i = 0 ; i<N ; i++){ //2차원 배열 크기만큼 ArrayList배열을 만들어준다.
            arrayLists[i] = new ArrayList<>();
        }

        for (int i = 0 ; i < N ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j = 0 ; j <N ; j++){
                if (Integer.parseInt(st.nextToken())==1){ //방향 관계가 있다면
                    arrayLists[i].add(j); //관계를 추가한다. i는 시작노드 j는 도착 노드
                }

            }
        }


        for (int i  = 0 ;  i < N ; i++){
            for (int j = 0 ;  j <  N ; j++){
                if(Direction_Graph(i,j)){ // visit [j] = true 라면 j 에 방문했다는 의미이다. 따라서 가는 경로가 있다.
                    sb.append("1 ");
                }else {
                    sb.append("0 ");
                }
               Arrays.fill(visit,false); //방문했던 기록을 초기화 시켜주어야 한다.
            }
            sb.append("\n");
        }

        System.out.print(sb);

    }

    public static boolean Direction_Graph (int start,int end){

        
        
        // 0 1 2 3 4 5 6 (arrayLists[i]
        
        // 3 6   4 0 6 2  arrayLists.get(0)
        //       5        arrayLists.get(1)
        
        for (int i = 0 ; i < arrayLists[start].size();i++){
            int nextNum = arrayLists[start].get(i);
            if ( !visit[nextNum]){
                visit[nextNum]=true; //방문할 노드는 true 변경하여준다.
                Direction_Graph(nextNum,end); 
            }
        }

        return visit[end]; //값이  true 라면 경로가 있다는 것이고 false 라면 경로가 없다는 것이다.
    }
}

 

[코드 : 플로이드- 와샬]

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

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        int[][] array = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer  st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                array[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //플로이드 - 와샬
        //array[i][j] = array[i][k] -> array[k][j]
        for (int k = 0; k < N; k++) { //거쳐가는점
            for (int i = 0; i < N; i++) { // 출발 노드
                for (int j = 0; j < N; j++) { //도착 노드
                    if (array[i][k] == 1 && array[k][j] == 1) { //이 관계여야 i -> j 가 성립한다.
                        array[i][j] = 1; //경로가 있다면 1
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(array[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }

}

처음 풀었던 코드가 더 오래 걸렸던 이유는 2차원배열의 인덱스마다 Direction_Graph(i,j)를 해주어 N*N번 연산을 매번 시켜줘야 했고 방문한 노드를 체크해주는 visit 배열도 매번 false로 초기화를 시켜야만했다. 이러한 과정들 때문에 시간이 더 오래 걸렸다.

 

플로이드 - 와샬 코드는 노드의 관계성을 3중 for문을 돌면서 시작 노드와 도착 노드의 관계가 성립하면 1로 표시하여 2차원 배열을 그대로 출력해주기만 하면 되기때문에 시간 단축이 되었다. 

 

 

[결과]

[결과 : 플로이드 - 와샬]