Recursive, Tree, Graph(DFS, BFS 기초) - 그래프 최단거리(BFS)

1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.

 

입력설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.

 

출력설명

1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

 

입력예제

6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5

 

출력예제

2 : 3
3 : 1
4 : 1
5 : 2
6 : 2

 

import java.util.*;

public class Main {
    static int n;
    static int m;
    static int[] ch;
    static int[] d;
    static List<List<Integer>> graph;

    public static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        ch[v] = 1;
        d[v] = 0;
        queue.add(v);
        while (!queue.isEmpty()) {
            int cv = queue.poll();
            for (int nv : graph.get(cv)) {
                if (ch[nv] == 0) {
                    ch[nv] = 1;
                    queue.add(nv);
                    d[nv] = d[cv] + 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        ch = new int[n + 1];
        d = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        BFS(1);
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + d[i]);
        }
    }
}