[BFS] 14. 그래프 최단 거리

<<풀이>>

 

이 문제는 1번 정점에서 각 정점까지의 최소 간선 수를 구하는 문제이다.

 

Level로 풀 수도 있지만, 그 외에 dis라는 배열을 사용했다. 이는 1에서 부터 해당 값까지 오기 위한 간선 의 수를 저장해두고 있다.

 

그리고 아직 등록이 되지 않은 값들을 연결되어 있던 이전 값들 까지 오기 까지의 간선의 수에 + 1을 해준다.

 

그렇게 해서 최종적으로 dis의 데이터는 인덱스 값을 1에서 2, 3, 4, 5 로 특정 위치로 간다고 명확하게 표시하고 그 때 간선 값을 가지고 있다.

 

*인덱스 값이 실제 값 1, 2, 3 등으로 표현해서 명확하게 하기 위해서 초기 배열 선언 부터 [n] 이 아닌 [n + 1]로 지정했다.

 

*만약 1 -> 2로 가는 것도 있지만 1 -> 3 -> 2로 가는 것도 있다면 어떻게 최소 간선인 것을 구분하지? 라는 생각을 초기에 했는데 생각해보니까 ch[] 라는 체크하는 배열로 통해서 이미 간 곳은 1로 되기 때문에 사전에 1 -> 2로 간 것이 있다면 1 -> 3 -> 2로 가는 것은 뺄 수 있는 것이다.

 

 

 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    static int n, m;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;
    public void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        ch[v] = 1;
        dis[v] = 0;
        queue.offer(v);
        while (!queue.isEmpty()) {
            int cv = queue.poll();
            for(int nv : graph.get(cv)) {
                if (ch[nv] == 0) {
                    ch[nv] = 1;
                    queue.offer(nv);
                    dis[nv] = dis[cv] + 1;
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n + 1];
        dis = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            graph.get(a).add(b);
        }
        T.BFS(1);
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]);

        }
    }
}

 

여기까지 DFS BFS 의 여러가지 문제 형식을 접해보았다. 이해는 했지만 아직까지 완벽히 내 것은 아닌 것 같다. 이제 부터 본격적으로 기출을 풀어 볼텐데 완전히 내 것이 될 수 있도록 공부해보자!!