[백준(Baekjoon)][자바(java)] 24444 : 알고리즘 수업 - 너비 우선 탐색 1 / 그래프와 순회

 

https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static List<List<Integer>> edge;
	static boolean visited[];
	static int vertex[], order;
	
	public static void bfs(int r) {
		visited[r] = true;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(r);
		int u;
		while (!queue.isEmpty()) {
			u = queue.remove();
			vertex[u] = order++;
			for (int v : edge.get(u)) {
				if (!visited[v]) {
					visited[v] = true;
					queue.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()),
			m = Integer.parseInt(st.nextToken()),
			r = Integer.parseInt(st.nextToken()) - 1, u, v, i;
		edge = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge.add(new ArrayList<>());
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			edge.get(u).add(v);
			edge.get(v).add(u);
		}
		br.close();
		
		for (i = 0; i < n; ++i)
			Collections.sort(edge.get(i));
		
		vertex = new int[n];
		order = 1;
		
		visited = new boolean[n];
		
		bfs(r);
		
		StringBuilder sb = new StringBuilder();
		for (int ver : vertex)
			sb.append(ver + "\n");
		System.out.println(sb.toString());
	}
}