너비 우선 탐색(Breadth First Search, BFS)은 완전 탐색 기법 중 하나로, 주로 최단 거리나 최단 시간 등 목표 상태에 도달할 수 있는 가장 빠른 경로를 탐색하는데 활용됩니다.

탐색 순서

BFS는 초기 상태에서 가장 가까운 상태부터 탐색합니다. 그 중 가장 먼저 목표 상태에 도달한 상태의 경로가 최단 경로가 됩니다.

BFS는 DFS와 달리 탐색 공간의 깊이에 제한이 없습니다. 목표 상태가 존재하기만 한다면 해당 목표를 찾을 수 있습니다. 대신 가까운 거리에 있는 모든 상태를 큐 자료구조에 넣기 때문에 공간 복잡도가 높습니다.

따라서 탐색 공간에 목표 상태가 있는지 검사할 때는 DFS, 최단 경로를 찾아야 할때는 BFS를 사용합니다.

큐 사용하여 구현하기

BFS는 큐 자료구조를 사용해서 구현합니다. 큐가 탐색 공간을 나타내고 상태를 전이시키며 탐색 공간에 추가하는 방식으로 탐색이 진행됩니다.

코드로 구현할때 다음과 같은 형식으로 짜여집니다.

//1. 방문 배열 만들기
boolean[] isVisited = new boolean[n];

//2. 큐 만들기
Queue<T> queue = new LinkedList<>();

//3. 상태 초기값 큐에 담기
queue.add(new State(초기값));

//4. 큐가 빌때까지 탐색 진행하기
while(!queue.isEmpty()){
	//5. 상태 뽑기
    State state = queue.poll();
    
    //6. 방문배열 확인 및 종료조건 확인
    if(isVisited[state]) continue;
    /*
    	종료조건
    */
    
    //7. 방문 처리
    isVisited[state] = true;
    
    //8. 전이할 다음 상태에 대한 유효성 검사
    /*
    	범위,유효성 검사 
    */
    
    //9.다음 상태 큐에 담기
    queue.add(new State(다음상태값));
   
}

BFS는 큐에 넣는 순서대로 상태를 방문합니다. 가장먼저 종료 조건을 타고 나오는 상태의 경로가 곧 최단 경로가 됩니다.