인프런 커뮤니티 질문&답변

이전 문제와 비슷하게 graph 인접리스트를 이용하고, ch 배열을 사용해여 이미 방문한 곳을 체크했습니다.

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

class Main {
  static int answer = 0;
  static ArrayList<ArrayList<Integer>> graph;
  static int n, m;
  static int[] dis, ch;
  public static void bfs(int v) {
    Queue<Integer> Q = new LinkedList<>();
    Q.offer(v);
    int L = 0;
    while (!Q.isEmpty()) {
      int len = Q.size();
      for (int i = 0; i < len; i++) {
        int cur = Q.poll();
        dis[cur] = L;
        for (int nv : graph.get(cur)) {
          if (ch[nv] == 0) {
            ch[nv] = 1;
            Q.offer(nv);
          }
        }
      }
      L++;
    }
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = null;
    st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
      graph.add(new ArrayList<>());
    }
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      graph.get(a).add(b);
    }
    ch = new int[n + 1];
    dis = new int[n + 1];
    ch[1] = 1;
    bfs(1);
    for (int i = 2; i <= n; i++) {
      System.out.println(i + " : " + dis[i]);
    }
  }
}