그래프 최단 거리(BFS)

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

입력

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

출력

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

입력예제 1

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.*;

class Main {
    static int n, m, answer = 0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch, dis;

    public void BFS(int v) {
        // 체크 배열
        ch[v] = 1;
        // 거리 값 배열
        dis[v] = 0;
        // 큐로 방문 체크 구현
        Queue<Integer> queue = new LinkedList<>();
        // 최초 값 넣고 시작한다.
        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);
                    // 해당 값의 거리를 +1 시킨다.
                    dis[nv] = dis[cv] + 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.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 = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);
        }
        T.BFS(1);
        for (int i = 2; i <= n; i++) {
            System.out.println(i + " : " + dis[i]);
        }
    }
}