99클럽 코테 스터디 5일차 TIL (24444번: 알고리즘 수업 - 너비 우선 탐색 1)

문제

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

 

---

학습 키워드

• BFS

 

시도

BFS를 사용해서 풀면된다.

 

풀이

• 무방향 그래프이므로 map에는 u와 v 양쪽 다 저장해야한다.
  • put(u, v);
  • put(v, u);
• 각 정점이 출력된 순서를 저장하는 orders와 출력 순서를 기억하기 위한 orderIndex를 선언한다.
• 탐색했는지 여부를 저장하기 위한 visited를 선언한다.
• BFS 방식으로 탐색하면서 각 정점이 추가되는 지점을 찾아 order에 기록한다.

import java.util.*;

public class Main {

	private static int N;
	private static int M;
	private static int R;
	private static Map<Integer, List<Integer>> map;
	private static int[] orders;
	private static int orderIndex = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		R = sc.nextInt();

		map = new HashMap<>();
		orders = new int[N + 1];

		for (int i = 0; i < M; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			map.putIfAbsent(u, new ArrayList<>());
			map.putIfAbsent(v, new ArrayList<>());
			map.get(v).add(u);
			map.get(u).add(v);
		}
		bfs(R);
		for (int i = 1; i <= N; i++) {
			System.out.println(orders[i]);
		}
	}

	private static void bfs(int R) {
		boolean[] visited = new boolean[N + 1];
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(R);
		visited[R] = true;
		orders[R] = ++orderIndex;
		while (!queue.isEmpty()) {
			int target = queue.poll();
			List<Integer> linked = map.get(target);
			Collections.sort(linked);
			for (int i = 0; i < linked.size(); i++) {
				if (visited[linked.get(i)]) {
					continue;
				}
				queue.offer(linked.get(i));
				visited[linked.get(i)] = true;
				orders[linked.get(i)] = ++orderIndex;
			}
		}
	}
}