[백준] 24445번: 알고리즘 수업 - 너비 우선 탐색 2 (JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static int order;
	static int[] check;

	public static void main(String[] args) throws Exception {
		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 R = Integer.parseInt(st.nextToken());
		
		for (int n = 0; n < N; n++) {
			graph.add(new ArrayList<Integer>());
		}
		
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			graph.get(u - 1).add(v - 1); 
			graph.get(v - 1).add(u - 1);		
		}
		
		for (ArrayList<Integer> g : graph) {
			Collections.sort(g, Comparator.reverseOrder());
		}
		
		// System.out.println(graph);
		
		check = new int[N];
		order = 1;
		
		// BFS
		Queue<Integer> q = new ArrayDeque<>();
		int start = R - 1;
		q.add(start); // 루트 노드(시작점)
		check[start] = order; // 방문한 시작점에 1번째 방문을 기록
		while (!q.isEmpty()) { // queue가 빌 때까지 반복한다.
			int currentNode = q.poll();
			// System.out.println("현재 노드: " + currentNode);
			// 가장 오래된 노드를 queue에서 꺼낸다.
			ArrayList<Integer> edges = graph.get(currentNode);
			// 그래프에서 조회한 뒤, 그 노드와 연결된 다음 노드들
			for (int nextNode: edges) {
				if (check[nextNode] != 0) {
					continue;
				}
				// System.out.println("다음 노드: " + nextNode);
				check[nextNode] = ++order;
				q.add(nextNode);
			}
			
		}
		
		for (int c: check) {
			System.out.println(c);
		}
	}

}