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

BFS: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

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

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 = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0}; // 상하좌우 

    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) 탐색하는 것이다.
  사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

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

너비 우선 탐색은 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다.
1.루트에서 시작한다.
2.자식 노드들을 [1]에 저장한다.
3.[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.
4.[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.
위의 과정을 반복한다. 모든 노드를 방문하면 탐색을 마친다.

BFS (Breadth-First-Search, 너비 우선 탐색) 알고리즘은 Queue를 사용해서 무제를 해결하면 된다.
1) 두 지점 사이의 최단 경로를 찾는 문제에 적합하다. 
2) FIFO (First In First Out) 원칙이다.

vs dfs