[JAVA] 너비 우선 탐색(BFS, Breadth-First Search)

BFS: 너비우선탐색

탐색과정

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복

처음 방문 했을 때만 방문 표시를 남기기 때문에 모든 칸이 큐에 1번씩 들어간다. 따라서 시간복잡도는 칸이 N개일 때 O(N)이다. 같은 원리로 행이 R개, 열이 C개인 2차원 평면을 BFS 탐색하면 시간복잡도는 O(RC)가 될 것이다.

dx, dy 상하좌우

 

import java.util.*;

public class Main {
    static int[][] board = {
        {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
        {1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    }; // 1이 파란 칸, 0이 빨간 칸에 대응
    static boolean[][] vis = new boolean[502][502]; // 해당 칸을 방문했는지 여부를 저장
    static int n = 7, m = 10; // n = 행의 수, m = 열의 수
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1}; // 상하좌우 

    public static void main(String[] args) {
        bfs(0, 0); // 시작점 (0, 0)에서 BFS 시작
    }

    // bfs 함수로 따로 분리
    static void bfs(int startX, int startY) {
        Queue<Pair> que = new LinkedList<>();
        vis[startX][startY] = true; // 시작점을 방문했다고 명시
        que.add(new Pair(startX, startY)); // 큐에 시작점 삽입

        while (!que.isEmpty()) {
            Pair cur = que.poll(); // 큐에서 현재 좌표를 가져옴
            System.out.print("(" + cur.x + ", " + cur.y + ") -> ");

            for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 탐색
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir]; // nx, ny에 dir 방향의 인접한 칸의 좌표가 들어감

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위를 벗어나면 무시
                if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문했거나 파란 칸이 아닐 경우 무시

                vis[nx][ny] = true; // (nx, ny)를 방문했다고 명시
                que.add(new Pair(nx, ny)); // 큐에 새로 방문한 좌표를 추가
            }
        }
    }

    // 좌표를 저장하는 Pair 클래스
    static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

잘못된 경우

1. 시작점에 방문했다는 표시를 남기지 않는다.
2. 큐를 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남겼다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

너비 우선 탐색

-루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
-시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

vs dfs