BFS 되짚어보기 (Java)

🧁 BFS의 개념

하나의 정점에서 시작해서 인접한 정점들을 먼저 탐색하고, 결국 갈 수 있는 모든 정점들을 방문하는 것

Queue를 선언하여 탐색하고자 하는 정점들을 관리합니다.
또한, visited 배열을 선언하여 정점의 방문 여부를 관리합니다.
(방문 여부를 관리하지 않으면 Queue에 이미 들어갔던 정점이 또 들어가서 끝나지 않을 수 있습니다.)

기본적인 흐름은 다음과 같습니다.

1. Queue에 시작 정점을 넣고

2. while문을 사용해 Queue가 빌 때까지 다음 로직을 반복합니다.
   1) Queue에서 정점 하나를 꺼냅니다.
   2) 해당 정점과 인접한 정점들을 하나씩 보면서,
   3) 각각의 정점을 방문했는지 확인 후,
   4) 방문하지 않은 경우에만 Queue에 그 정점을 넣습니다.

🍦 코드

그래프가 위와 같다고 가정할 때,
노드 1부터 BFS를 시작하는 코드는 아래와 같습니다.

import java.util.LinkedList;
import java.util.Queue;

public class BfsTest {

	private static boolean visited[];
	private static int graph[][] = { {}, { 2, 3, 4 }, { 1, 4 }, { 1, 5 }, { 1, 2 }, { 3 } };

	public static void main(String[] args) {
		visited = new boolean[6];
		Queue<Integer> q = new LinkedList<>();
		q.add(1);
		visited[1] = true;
		while (!q.isEmpty()) {
			int nodeIdx = q.poll();
			System.out.print(nodeIdx + " ");
			for (int node : graph[nodeIdx]) {
				if (!visited[node]) {
					visited[node] = true;
					q.add(node);
				}
			}
		}
	}

}