[알고리즘] BFS 어떨 때 사용해야할까?

1️⃣ 연결된 영역 찾기 (Connected Component)

특징

• 상하좌우로 연결된 것
• 덩어리 개수 세기

예시 문제

• 백준 1012 유기농 배추
• 백준 2667 단지번호붙이기
• 백준 4963 섬의 개수

예시 맵

1 1 0 0
1 0 0 1
0 0 1 1

BFS로 탐색하면

덩어리 1: (0,0),(0,1),(1,0)
덩어리 2: (1,3),(2,2),(2,3)

➡️ 덩어리 수 = 2

코드 패턴

if (map[i][j] == 1 && !visited[i][j]) {
    bfs(i,j);
    count++;
}

 

2️⃣ 최단 거리 문제

 

BFS는 가중치 없는 그래프에서 최단 거리를 구할 때 사용

특징

• 몇 번 이동해야 하는지
• 최단 거리

예시 문제

• 백준 2178 미로 탐색
• 백준 1697 숨바꼭질
• 백준 7576 토마토

예시

S 0 0
1 1 0
0 0 E

BFS는

S → 1칸
→ 2칸
→ 3칸

이렇게 레이어별로 탐색해서 최단 거리를 찾음.

 

코드 패턴

dist[nx][ny] = dist[x][y] + 1;

 

3️⃣ 상태 탐색 문제 (그래프 확장)

 

어떤 상태에서 다음 상태로 이동하는 문제.

특징

• 좌표가 아니라 상태
• 큐에 상태를 넣음

예시 문제

 

백준 1697 숨바꼭질

x → x+1
x → x-1
x → x*2

BFS로 탐색

5
→ 6
→ 4
→ 10
→ ...

최단 시간 찾기

 

BFS 기본 템플릿

 

 

2차원 BFS

Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x,y});
visited[x][y] = true;

while (!q.isEmpty()) {
    int[] cur = q.poll();

    for (int d=0; d<4; d++) {
        int nx = cur[0] + dx[d];
        int ny = cur[1] + dy[d];

        if (범위 밖) continue;
        if (visited[nx][ny]) continue;
        if (map[nx][ny] == 0) continue;

        visited[nx][ny] = true;
        q.add(new int[]{nx,ny});
    }
}

BFS 문제 알아보는 방법

① 연결된 영역

상하좌우
붙어있는
연결된

➡️ BFS / DFS

② 최소 이동 횟수

최소
몇 번 이동
최단 거리

➡️ BFS

③ 단계 확산

하루 후
시간 후
전파

➡️ BFS