너비 우선 탐색(Breadth-Frist-Search)

BFS(너비 우선 탐색)의 정의

BFS(Breadth-First Search)는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 차례대로 탐색하는 방식을 말한다.
큐(Queue) 자료구조를 사용하며 탐색 순서는 레벨 단위로 진행된다.

---

BFS를 사용하는 경우

1. 특정 지점에서 다른 지점까지의 최단 거리를 구할 때
   ex: 미로에서 출구까지의 최단 거리 찾기, GPS 경로 탐색 등

2. 특정 거리 내에서(같은) 조건을 만족하는 노드를 찾을 때
   ex: 친구 추천 시스템(친구의 친구 탐색)

3. 특정 범위 내에서 그룹을 찾을 때
   ex: 섬의 개수 찾기 문제

---

BFS의 장점과 단점

• BFS의 장점

1. 최단 거리를 보장
   BFS는 최단 거리를 보장하는 탐색 방법이므로 경로 찾기 문제에서 매우 유용하다.

2. 모든 경우를 빠짐없이 탐색
   DFS와 달리 특정 조건을 충족하는 경우를 놓치지 않고 탐색한다.

3. 재귀 호출 없이 큐(Queue)만 사용
   DFS는 재귀 호출이 많으면 스택 오버플로우가 발생할 수 있지만, BFS는 큐만 사용하여 안정적인 탐색이 가능하다.

• BFS의 단점

1. 메모리 사용량이 많음
   모든 노드를 큐에 저장하므로 탐색 공간이 넓거나 노드가 많을 경우 메모리 부담이 커질 수 있다.

2. 목적지가 멀 경우 속도가 느려짐
   깊이가 깊은 경우에는 DFS보다 탐색 시간이 오래 걸릴 수 있다.

---

BFS를 활용한 거리두기 문제 해결

프로그래머스 - 2021 카카오 채용연계형 인턴십 - 거리두기 확인하기

문제의 주 목표는 대기실이 5x5 크기의 2차원 배열로 주어질 때 응시자가 앉아있는 자리(P)들이 맨해튼 거리 2 이내에서 서로 마주하지 않는지 검증해야하므로 최단경로를 확인하는 BFS를 사용한다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Test_79_CheckDistancing {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        for (int i = 0; i < 5; i++) {
            answer[i] = checkRoom(places[i]) ? 1 : 0;
        }

        return answer;
    }

    private boolean checkRoom(String[] room) {
        List<int[]> people = new ArrayList<>();

        // 응시자 위치 저장
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (room[i].charAt(j) == 'P') {
                    people.add(new int[]{i, j});
                }
            }
        }

        // 각 응시자에 대해 거리두기 확인
        for (int[] person : people) {
            if (!bfs(person[0], person[1], room)) {
                return false;
            }
        }

        return true;
    }

    // bfs(너비 우선 탐색)을 사용해서 응시자 탐색
    private boolean bfs(int x, int y, String[] room) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[5][5];

        queue.add(new int[]{x, y, 0}); // x, y, 거리
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0], cy = current[1], dist = current[2];

            if (dist >= 2) continue; // 맨해튼 거리 2까지만 검사

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !visited[nx][ny]) {
                    if (room[nx].charAt(ny) == 'P') return false; // 거리두기 위반
                    if (room[nx].charAt(ny) == 'O') {
                        queue.add(new int[]{nx, ny, dist + 1});
                    }
                    visited[nx][ny] = true;
                }
            }
        }
        return true;
    }
}

다음에는 BFS와 함께 사용되는 DFS(깊이 우선 탐색)에 대해 정리해봐야겠다.