넓이우선탐색 BFS(Breadth-First Search)

BFS(Breadth-First Search)는 너비 우선 탐색이라고 하며, 그래프나 트리에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. 주로 최단 경로 문제나 모든 정점을 방문해야 하는 경우에 사용됩니다.

 

 

• 큐(Queue) 자료구조를 사용하여 구현합니다.
• 시작점에서 가까운 정점부터 탐색하며, 같은 거리의 정점들을 먼저 모두 방문한 후, 다음 거리의 정점들을 탐색합니다.
• 최단 경로 보장: 모든 간선의 가중치가 동일하거나 1로 간주될 경우, BFS는 시작점에서 목표점까지의 최단 경로를 보장합니다.

package bfs;

import java.util.*;

public class MazeSolver {
    public static void main(String[] args) {
        int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
        };

        int[] start = {0, 0}; // 시작점
        int[] end = {4, 4};   // 목표점

        int shortestPath = bfsMaze(maze, start, end);
        System.out.println("최단 경로 길이: " + shortestPath); // 출력: 최단 경로 길이: 8
    }

    public static int bfsMaze(int[][] maze, int[] start, int[] end) {
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우

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

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

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int distance = current[2];

            // 목표 지점 도달
            if (x == end[0] && y == end[1]) {
                return distance;
            }

            // 상하좌우 탐색
            for (int[] dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !visited[nx][ny] && maze[nx][ny] == 0) {
                    queue.add(new int[] {nx, ny, distance + 1});
                    visited[nx][ny] = true;
                }
            }
        }

        return -1; // 경로가 없는 경우
    }
}