너비 우선 탐색 (BFS)

# collections.deque 로 O(1) pop
from collections import deque
import sys
input = sys.stdin.readline
​
n, m, s = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  adj[u].append(v)
  adj[v].append(u)
​
dist = [-1] * (n + 1)
q = deque([s])
dist[s] = 0
​
while q:
  u = q.popleft()
  for v in adj[u]:
      if dist[v] == -1:
          dist[v] = dist[u] + 1
          q.append(v)
​
print(*dist[1:])

// ArrayDeque 사용, O(V + E)
import java.util.*;
import java.io.*;
​
public class Main {
  static List<Integer>[] adj;
  static int[] dist;
  
  static void bfs(int s) {
      Queue<Integer> q = new ArrayDeque<>();
      dist[s] = 0;
      q.add(s);
      
      while (!q.isEmpty()) {
          int u = q.poll();
          for (int v : adj[u]) {
              if (dist[v] == -1) {
                  dist[v] = dist[u] + 1;
                  q.add(v);
              }
          }
      }
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      
      adj = new ArrayList[n + 1];
      for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
      dist = new int[n + 1];
      Arrays.fill(dist, -1);
      
      for (int i = 0; i < m; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      
      bfs(s);
      for (int i = 1; i <= n; i++)
          System.out.print(dist[i] + " ");
      System.out.println();
  }
}