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

1. BFS(너비 우선 탐색)

BFS vs DFS

• 그래프 탐색
  - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
  - 알고리즘 문제를 풀다보면 2차원 배열이 주어지고 탐색을 하며 특정 값을 구하라는 문제가 많은데 DFS와 달리 시간복잡도가 까다롭게 설정되어있고 최단경로를 찾는 문제일 때 주로 사용.

-동작과정

1. 큐 선언(2차원 배열이라면 Point 클래스를 활용) 및 시작 포인트 큐에 추가&&방문체크
2. while(!Queue.isEmpty()) 큐가 없어질 때까지 반복
3. Queue에서 poll하여 탐색 시작
4. 방향벡터를 이용해서 for문 4방탐색

• 다음 행선지 NULL체크
• 탈출 포인트 선언 (예를 들어 목적지 좌표에 도착했다면)
• 장애물 및 탐색하면 안되는 곳이라면 continue로 탈출
• 탐색할 수 있는 곳이라면 방문체크 및 큐 추가 (제약사항들에 대한 조건문 추가)

-완전탐색 방식

• Queue자료형의 선입선출 특성을 활용
• 현재 지점에서 4방향에 탐색할 수 있는 곳들을 전부 큐에 추가
• 큐에 추가할 때는 한 개의 전역변수 느낌이 아닌 new키워드로 다른 객체를 추가함으로써 재귀와 같이 별도의 데이터를 관리
• 추가된 큐에 대해 한 개씩 poll해보며 완전탐색
• DFS의 경우 재귀스택을 활용한 좌표 별 데이터 관리
• BFS는 개별 객체를 통해 좌표 별 데이터 관리 (즉, 바뀌어야할 매개변수가 있다면 객체 멤버변수를 활용)

-특성

• 최단경로를 찾기위한 알고리즘으로써 DFS에 비해 속도면에서 우위를 가짐
• 미로찾기와 같은 최우선의 특정 경로를 찾는 문제에서 BFS를 떠올릴 수 있음
• DFS의 경우 먼저 탐색한 곳 쪽으로 계속 탐색을 진행하지만 BFS의 경우 현재좌표 근처로 확산하며 탐색.
  • DFS : 4.0 → 3.0 → 2.0 → 1.0 → 0.1 → …
  • BFS : 4.0 → 3.0 → 4.1 → 2.0 → 4.2 → …

-구현

1. 그래프의 경우 (간선의 유무로만 판단하고 연결되어 있는 노드에 대해서만 탐색)

public class Main{
    static int N, M, V; //정점 수, 간선 수, 시작 노드
    static int[][] graph;
    static boolean[] visited;

    public static void main(String[] args) {
				/*
				이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언
				*/
        bfs(V);
    }

    //너비 우선 탐색 (그래프로 풀 경우 간선의 존재 유무만 체크하면 됨)
    static void bfs(int idx) {
        Queue<Integer> queue = new LinkedList<Integer>(); //큐 선언

        queue.add(idx); //큐에 시작지점을 추가
        visited[idx] = true; //방문체크

        while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프
            int s =queue.poll(); //현재 큐에 들어있는 맨 앞의 값을 꺼냄
            for(int i =1; i< graph.length;i++){ //그래프의 길이만큼 반복하면서
                if(graph[s][i] == 1 && !visited[i]){ //간선이 있을 때&&방문하지 않은 경우
                    queue.add(i); //큐에 계속해서 추가
                    visited[i] = true; //방문체크
                }
            }
        }
    }
}

2. 2차원 좌표를 활용한 4방향 탐색을 하는 경우

Point 클래스를 이용하여 큐를 통한 탐색을 진행하면서도 그때의 데이터를 저장할 수 있음.

멤버 인스턴스 변수를 활용 및 큐에 추가할 때마다 서로다른 객체를 만들어서 추가해줌으로써 큐에서 추출할 때마다 해당좌표의 값을 기억하고 탐색을 진행할 수 있음.

class Point{ //좌표값을 저장하기 위한 Point 클래스
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{
    static int[] dx = new int[] {-1, 0, 1, 0}; //방향벡터
    static int[] dy = new int[] {0, 1, 0, -1}; //방향벡터
    static int N, M, V; //정점 수, 간선 수, 시작 노드
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) {
				/*
				이 곳에 입력 및 배열 초기화를 진행하고, 배열크기에 맞게 visited배열 선언
				*/
        bfs(0, 0); //어디서부터 탐색을 할 지
    }

    //너비 우선 탐색 (그래프가 아닌 단순 2차원 배열 좌표값을 활용할 때
    static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>(); //큐 선언

        visited[x][y] = true; //시작지점 방문체크
        q.offer(new Point(x,y)); //큐에 시작지점 추가

        while(!queue.isEmpty()){ //큐가 빌 때까지 무한루프
            Point p = q.poll(); // 맨 앞의 큐를 꺼내고
            for (int i = 0; i < 4; i++) { //큐에서 꺼낸 인덱스로부터 사방탐색
                if (p.x + dx[i] < 0 || p.x + dx[i] > N - 1 || p.y + dy[i] < 0 || p.y + dy[i] > N - 1) continue; //Null 예외 처리
                if(특정 조건 값){
                    visited[p.x + dx[i]][p.y + dy[i]] = true; //방문 체크
                    q.offer(new Point(p.x + dx[i], p.y + dy[i])); //탐색을 위한 큐 추가
                }
                //4방탐색을 돌면서 해야할 조건들을 추가**
            }
        }
    }
}