• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• Queue를 사용 (FIFO)
• 이미지 출처: 나노 바나나 프로 (Nano Banana Pro)

문제 유형

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
• 미로 찾기
• 검색 대상의 규모가 크지 않은 경우

코드 예시

import java.io.*;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N,T;
	static int arr[][];
	static int visited[];
	
	static void bfs(int start) {
		Queue<Integer> q = new ArrayDeque<>();
		q.add(start);
		visited[start] = 1;
		while(!q.isEmpty()) {
			int now = q.remove();
			for(int i=1; i<N+1; i++) {
				
				if(arr[now][i] == 0)continue;
				if(visited[i] !=0)continue;
				
				q.add(i);
				
				visited[i] = visited[now]+1;
			}
		}
	}
	
	public static void main(String[] args) {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1][N+1];
		visited = new int[N+1];
		for(int i=0; i<T; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			arr[from][to] = 1;
			arr[to][from] = 1;
		}
		
		bfs(0);
		
		for(int i=0; i<N; i++) {
			System.out.println(visited[i]-1);
		}
	}
		
}