[인프런] 07_14 그래프 최단거리(BFS)

📖  문제

---

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

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

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

     

    

    그래프 예시

    

    출력

⚠️  주의사항

---

• 원래 갔던 곳으로 다시 돌아가지 않게 체크용 배열 추가
• 이중 리스트

 

✍️  이해

---

**
 * 1. 07_13과 같은 방법으로 queue 생성, 체크를 위한 배열 말고도 최단거리 배열 추가
 * 2. Queue 현재 값 추가
 * 3. Queue 빈 값이 될 때까지 반복
 *  3-1. Queue 현재 지점 빼와서 그 지점의 list를 체크배열에서 확인 (for-each 사용)
 */

 

✏️  풀이

---

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

public 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 currentNum = queue.poll(); // 현재 지점
            for (int nv : graph.get(currentNum)) {
                if (ch[nv] == 0) {
                    ch[nv] = 1;
                    queue.offer(nv);
                    dis[nv] = dis[currentNum] + 1;

                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.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 = sc.nextInt();
            int B = sc.nextInt();
            graph.get(A).add(B);
        }

        T.BFS(1);
        for (int i = 2; i <= N; i++) {
            System.out.println(i + " : " + dis[i]);
        }
    }
}

---