[알고리즘] BFS(Breadth-First Search) - 너비우선탐색

BFS(Breadth-First Search)

너비우선탐색
그래프 완전 탐색 기법 중 하나 - 큐를 이용해서 그래프의 모든 노드 탐색
시작 노드에서 출발 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
큐에 인접한 노드 혹은 노드의 좌표들을 넣어준다
큐가 비었다면? 인접 노드들이 없으므로 탐색이 종료된다

기능	특징	시간복잡도
그래프 완전 탐색	FIFO(선입선출) 탐색 Queue자료구조 이용	O(V + E ) v : 노드 수 E : 에지 수

* 경로가 여러개 일 때 최단 경로를 보장
 

너비우선탐색 핵심이론

• 한번 방문한 노드를 방문하면 안 됨 : 노드 여부를 체크할 배열이 필요
• 그래프 : 인접 리스트
• 큐를 이용한 탐색

import java.util.LinkedList;
import java.util.Queue;
 
public class Bfs {
    public static void main(String[] args) {
        // 각 노드가 연결상태를 2차원 배열로 표현
        int[][] graph = {{}, {2, 3}, {4}, {5, 6}, {2}, {5, 7}, {3}, {7}};
 
        // 방문처리에 사용 할 배열
        boolean[] visited = new boolean[graph.length];
 
        // 시작 노드
        int start = 1;
 
        // 큐 생성
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
 
        // 현재 노드를 방문 처리
        visited[start] = true;
 
        // 큐가 비었을 때 까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int node = queue.poll();
            System.out.print(node + " -> ");
 
            // 인접한 노드 중 아직 방문하지 않은 원소들을 큐에 삽입
            for (int index : graph[node]) {
                if (!visited[index]) {
                    queue.add(index);
                    visited[index] = true;
                }
            }
        }
    }
}

1. 방문 배열 선언
2. 거리 배열 선언
int [] dx = {-1,1,0,0}
int [] dy = {0,0,-1,1}
// 거리 계산
3. bfs안에 queue 선언
Queue<> q = new LinkedList<>();
큐에 위치 넣기
들어가 있는 위치가 있을때까지 while 문 돌리기
4. for문의 여부
시작점이 여러개 일때 - main 안
시작점이 하나일때 - bfs 안 - bfs(0,0) 또는 주어진 시작점에서 시작