[백준] 경로 찾기 : 11403 : Java - BFS, 최단 경로 (S1)

1. 문제

11403번: 경로 찾기

 

• i번째 숫자가 j번째에 도달할 수 있는지 출력한다. 가능하면 1, 불가능하면 0을 출력

---

 

 

2. 어떻게 풀까?

입력으로 주어지는 형식이 인접행렬일 뿐 결국 간선의 정보이다. 그러므로 평소 풀던것 처럼 `ArrayList []`를 생성하여 간선의 정보를 저장한 뒤, 1부터 N번째 숫자를 차례로 BFS 탐색을 진행하기로 했다. 만약 1을 시작으로 BFS 함수를 호출하면 1에서 다른 요소인 {2,3,4,5,6} 에 도달할 수 있는 탐색을 통해 알아낸다. 

// 1부터 N까지 각 BFS 탐색 진행
        for(int row =1; row<=N; row++){
            if(graph[row].size() > 0){
                boolean [] isVisited = new boolean[N+1];
                BFS(isVisited, row);
            }
        }

 

이때 start요소에 대해 `isVisited = true`를 하면  안된다. 문제의 조건은 도달할 수 있는 거리가 양수일 때만 1을 출력하라고 했다. 그러므로 다른 요소를 걸쳐서 탐색을 할 수 있는지를 확인 해야한다.

static void BFS(boolean [] isVisited, int start){
        Queue<Integer> que = new LinkedList<>();
        // 바로 본인한테 가능 경우는 0이여서 양수가 아님, 다시 돌아올 수 있는 경우를 확인 해야함.
        // 그러므로 isVisited = true X
        que.add(start);

        while(!que.isEmpty()){
            int current = que.poll();

            for(int next : graph[current]){
                if(!isVisited[next]){
                    que.add(next);
                    isVisited[next] = true;
                    result[start][next] = 1;
                }
            }
        }

    }

 

모든 탐색이 종료되면 결과를 출력한다. 여기까지가 BFS을 이용한 방법이었다. 하지만 다른 방법도 있다. 바로 플로이드 와샬 알고리즘을 쓰는 것이다.

 	for(int row=1; row<=N; row++) {
            for (int col = 1; col <= N; col++) {
                bw.write(result[row][col] +" ");
            }
            bw.write("\n");
        }

 

---

 

 

3. 다른 방법. 플로이드 와샬 알고리즘

플로이드 와샬 알고리즘
모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘

핵심 아이디어는 '거쳐가는 정점'을 기준으로 한다는 것이다.
즉, i에서 j까지 가는 것과 i에서 k로 가고, k에서 j로 가는 것은 같다.

 

모든 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘으로 플로이드 와샬 알고리즘이 많이 쓰인다. 알아두고 가자! 

        // i에서 j까지 갈 수 있는가?
        // i에서 k로 가고, k에서 j로 갈 수 있는가?
        for(int k=1; k<=N; k++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    if(array[i][k] == 1 && array[k][j] == 1)
                        array[i][j] = 1;
                }
            }
        }

 

 

 

4.1  전체 코드 - BFS

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

public class Main {
    static ArrayList<Integer> [] graph;
    static int [][] result;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N+1];
        result = new int[N+1][N+1];
        for(int i=0; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int row=1; row<=N; row++){
            StringTokenizer st= new StringTokenizer(br.readLine());
            for(int col=1; col<=N; col++){
                int num = Integer.parseInt(st.nextToken());
                if(num == 1)
                    graph[row].add(col);
            }
        }

        for(int row =1; row<=N; row++){
            if(graph[row].size() > 0){
                boolean [] isVisited = new boolean[N+1];
                BFS(isVisited, row);
            }

        }

        for(int row=1; row<=N; row++) {
            for (int col = 1; col <= N; col++) {
                bw.write(result[row][col] +" ");
            }
            bw.write("\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }

    static void BFS(boolean [] isVisited, int start){
        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        while(!que.isEmpty()){
            int current = que.poll();

            for(int next : graph[current]){
                if(!isVisited[next]){
                    que.add(next);
                    isVisited[next] = true;
                    result[start][next] = 1;
                }
            }
        }

    }
}

 

 

4.2  전체 코드 - 플로이드 와샬

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

public class Main {
    static ArrayList<Integer> [] graph;
    static int [][] array;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 변수 선언, 초기화
        int N = Integer.parseInt(br.readLine());
        array = new int[N+1][N+1];


        // 간선 추가
        for(int row=1; row<=N; row++){
            StringTokenizer st= new StringTokenizer(br.readLine());
            for(int col=1; col<=N; col++){
                array[row][col] = Integer.parseInt(st.nextToken());
            }
        }

        // i에서 j까지 갈 수 있는가?
        // i에서 k로 가고, k에서 j로 갈 수 있는가?
        for(int k=1; k<=N; k++){
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    if(array[i][k] == 1 && array[k][j] == 1)
                        array[i][j] = 1;
                }
            }
        }

        for(int row=1; row<=N; row++) {
            for (int col = 1; col <= N; col++) {
                bw.write(array[row][col] +" ");
            }
            bw.write("\n");
        }
        bw.flush();

        bw.close();
        br.close();
    }

}

 

성능은 둘이 비슷하다. 아무래도 모든 정점을 탐색하기 위해 루프를 도는 것은 같아서 시간은 비슷하지만 플로이드 알고리즘이 구현하기는 더 쉽다.