[Java] BFS(Breadth First Search)

💡BFS(Breadth First Search)

: 너비 우선 탐색 이라는 의미를 가진 BFS는 쉽게말해 가까운 노드부터 탐색하는 알고리즘이다.

BFS구현에는 선입선출 방식인 큐 자료구조를 사용한다.

---

💡BFS 동작 방식

1. 탐색 시작 노드를 큐에 삽입 후 방문처리
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

1️⃣ 시작노드인 1을 큐에 삽입하고 방문처리함

2️⃣ 큐에서 1을 꺼내고 방문하지 않은 2, 3, 8을 모두 큐에 삽입 후 방문처리함

3️⃣ 큐에서 노드 2를 꺼낸 뒤, 방문하지 않은 인접노드 7을 큐에 삽입 후 방문처리함

4️⃣ 큐에서 노드 3을 꺼내고 방문하지 않은 인접노드인 4,5를 모두 큐에 삽입 후 방문처리

5️⃣ 큐에서 노드 8을 꺼내고 방문하지 않은 인접노드가 없으므로 무시한다

6️⃣ 큐에서 노드7을 꺼내고 방문하지 않은 인접 노드 6을 삽입하고 방문처리함

7️⃣ 남아있는 노드에 방문하지 않은 인접 노드가 없음
→ 따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같음

💡 1 → 2→ 3→ 8→ 7→ 4→ 5→ 6

---

💡BFS코드 (Java)

import java.util.ArrayDeque;
import java.util.Queue;

public class BASIC_BFS_DFS {

static int[][] map = { // 0 index는 dummy
        {0,  0,  0,  0,  0,  0,  0},
        {0, 11, 12, 13, 14, 15, 16},
        {0, 21, 22, 23, 24, 25, 26},
        {0, 31, 32, 33, 34, 35, 36},
        {0, 41, 42, 43, 44, 45, 46},
        {0, 51, 52, 53, 54, 55, 56},
        {0, 61, 62, 63, 64, 65, 66},
};

// 자료 구조 
static Queue<Node> queue = new ArrayDeque<>();
static boolean[][] visit;

// 사방탐색 delta 상 - 하 - 좌 - 우
static int[] dy = { -1, 1, 0, 0 };
static int[] dx = {  0, 0,-1, 1 };

static int COUNT;

public static void main(String[] args) {
    // bfs
    COUNT = 0;
    visit  = new boolean[7][7];
    bfs( 1, 1 );
}

// 방문했던 곳을 다시 시작하기 위해서 잠깐 담아놓는 자료구조가 필요 Queue
// 별도의 클래스를 일반적으로 만든다. ( 클래스 또는 배열 )
// visit
// 한번만 호출
static void bfs( int y, int x ) {

    // 최초 y, x 를 이용해서 Node 한 개를 담는다.
    queue.offer(new Node(y, x));
    visit[y][x] = true;

    while( ! queue.isEmpty() ) {

        Node node = queue.poll();
        COUNT++;

        //System.out.println(node);

        for (int d = 0; d < 4; d++) {
            int ny = node.y + dy[d];
            int nx = node.x + dx[d];

            if( ny < 1 || nx < 1 || ny >=7 || nx >= 7 || visit[ny][nx]) continue;

            queue.offer(new Node(ny, nx));
            visit[ny][nx] = true;
        }

    }

    System.out.println("BFS : COUNT : " + COUNT);
}

static class Node{
    int y, x;

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

    @Override
    public String toString() {
        return "Node [y=" + y + ", x=" + x + "]";
    }
}
}

---

참고: Copy of 이것이 코딩테스트다