[백준 / JAVA] 24444. 알고리즘 수업 - 너비 우선 탐색 1

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

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

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

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

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

		int[] visited = new int[N + 1];
		List<Integer>[] edge = new LinkedList[N + 1];

		for (int i = 1; i <= N; i++) {
			edge[i] = new LinkedList<>();
		}

		for (int i = 0; i < M; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			edge[u].add(v);
			edge[v].add(u);
		}

		// 각 정점으로부터 연결된 간선 리스트를 오름차순 정렬
		for (int i = 1; i < edge.length; i++) {
			Collections.sort(edge[i]);
		}

		Queue<Integer> queue = new LinkedList<>();
		int cnt = 0;

		queue.add(R);
		visited[R] = ++cnt;

		while (!queue.isEmpty()) {
			int curr = queue.poll();

			// 다음 정점들 큐에 넣기
			for (int i : edge[curr]) {
				if (visited[i] == 0) {
					queue.add(i);
					visited[i] = ++cnt;
				}
			}
		} // while문 끝

		// 출력
		for (int i = 1; i < visited.length; i++) {
			System.out.println(visited[i]);
		}
	}
}

 

💬 풀이 과정

• 각 정점에 연결된 간선들을 입력받아 간선 집합에 넣을 때, 양방향임을 생각해서 두 정점의 배열에 기록
• 방문 순서를 저장할 visited 배열을 생성

💡 깨달은 점

1. BFS의 기본 구조

• 너비를 우선으로 방문하는 알고리즘

2. Collections.sort(리스트명)

• 리스트를 오름차순 정렬하고 싶을 때 사용

3. 자료 구조 List<Integer>[]

• 정수형 값을 저장할 연결리스트 자료형의 배열이라는 자료구조를 생성