BFS(너비 우선 탐색) 알고리즘

최대한 넓게 이동하고, 갈 곳이 없을 때 아래로 이동하는 알고리즘

너비 우선 검색이란 무엇입니까?

루트 노드(또는 임의의 노드)에서 시작하여 다음 레벨로 이동하기 전에 같은 레벨의 이웃 노드를 먼저 탐색하는 그래프 순회 알고리즘으로

DFS 와 BFS 비교 그림 사진

데이터 구조: 큐

Queue(큐) 데이터 구조에 의존
큐는 노드 처리의 FIFO(선입선출) 순서를 유지하여 알고리즘의 너비 우선 특성을 유지

너비 우선 탐색의 단계

1. 초기화

• 처리할 노드를 저장할 큐 생성
• 시작 노드를 방문한 것으로 표시하고 큐에 추가

2. 탐색

• 큐가 비어 있지 않은 동안:
  • 큐에서 노드를 추출합니다.
  • 이웃을 탐색하고 방문하지 않은 이웃을 큐에 넣습니다.
  • 재방문하지 않도록 방문한 노드에 표시 .

3. 종료

• 큐가 비어 있을 때 알고리즘이 종료되며, 이는 모든 도달 가능한 노드가 방문되었음을 의미합니다.

BFS와 DFS의 차이

특징	너비 우선 탐색 (BFS)	깊이 우선 탐색 (DFS)
탐색 순서	수평으로 레벨 단위 탐색	수직으로 최대한 깊게 이동하고 후진
구현 방식	일반적으로 큐(QUEUE) 사용	일반적으로 스택(STACK) 또는 재귀(RECURSION) 사용
시간복잡도	조건 내의 모든 노드를 탐색하기 때문에 시간복잡도는 동일
메모리 사용	일반적으로 더 많은 메모리 사용	일반적으로 덜 많은 메모리 사용
경로 특성	최단 경로를 구해야 하는 경우 짧은 경로가 중요한 경우 적합	최경로의 특징을 저장해야 하는 경우 메모리 사용이 중요한 경우 적합

BFS로 풀어본 백준 문제

백준 1697번 숨바꼭질 문제로 바로가기

import java.io.*;
import java.util.*;

public class Main {
    static int N;  // 시작 위치
    static int K;  // 목표 위치

    static int visited[] = new int[100001];  // 방문한 노드를 기록하는 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();
        String[] inputs = input.split(" ");
        
        N = Integer.valueOf(inputs[0]);
        K = Integer.valueOf(inputs[1]);
        
        int result = bfs(N);
        System.out.println(result);
    }

    private static int bfs(int node) {
        Queue<Integer> queue = new LinkedList<Integer>();

        queue.add(node);  // 시작 노드를 큐에 넣음
        int index = node;
        int n = 0;
        visited[index] = 1;  // 시작 노드를 방문했음을 표시하고 거리를 1로 설정

        // 큐가 비어있을 때까지 BFS를 수행
        while (queue.isEmpty() == false) {
            n = queue.remove();  // 노드를 큐에서 꺼냄

            if (n == K) {
                // 현재 노드가 목표 노드인 경우 거리를 반환
                return visited[n] - 1;  // 시작 노드의 거리를 제외하기 위해 1을 뺌
            }

            // 인접한 노드들을 탐색
            if (n - 1 >= 0 && visited[n - 1] == 0) {
                visited[n - 1] = visited[n] + 1;  // 왼쪽 인접 노드를 표시하고 큐에 넣음
                queue.add(n - 1);
            }
            if (n + 1 <= 100000 && visited[n + 1] == 0) {
                visited[n + 1] = visited[n] + 1;  // 오른쪽 인접 노드를 표시하고 큐에 넣음
                queue.add(n + 1);
            }
            if (2 * n <= 100000 && visited[2 * n] == 0) {
                visited[2 * n] = visited[n] + 1;  // 두 배의 인접 노드를 표시하고 큐에 넣음
                queue.add(2 * n);
            }
        }
        // 목표 노드에 도달하지 못하면 -1을 반환
        return -1;
    }
}