[알고리즘] BFS(Breadth - First Search), 송아지 찾기

BFS(Breadth-First Search) 알고리즘은 그래프 탐색을 위한 대표적인 알고리즘 중 하나이다.

그래프를 탐색하면서 같은 레벨에 있는 노드를 모두 방문한 후 다음 레벨로 이동하여 탐색하는 방법을 사용한다.

이 알고리즘은 그래프에서 최단 경로를 찾는 문제를 푸는 데 활용된다.

BFS 알고리즘은 다음과 같이 동작한다.

시작 노드를 큐(queue)에 추가.
큐에서 노드를 하나 꺼내어 방문.
해당 노드와 인접한 노드들 중 방문하지 않은 노드를 모두 큐에 추가.
큐가 빌 때까지 2-3 단계를 반복.
이 알고리즘을 구현할 때는 큐를 사용하여 노드를 관리하며, 방문한 노드를 표시하기 위한 visited 배열을 사용.

BFS 알고리즘의 시간 복잡도는 노드의 수를 V, 간선의 수를 E라고 할 때 O(V+E)다.

 

대표적인 예시 문제로는 송아지 찾기가 있다.

 

송아지 찾기는 현수가 잃어버린 송아지를 찾는 문제이다.

 

현수는 한번에 1, -1, 5만큼 움직일 수 있다.

 

이때 현수가 송아지를 찾는 최단 경로를 구하라.

(단, 좌표는 1 ~ 10000까지의 범위를 허용한다.)

 

이때 문제의 풀이 과정은 아래와 같다.

 

1. 현수 s, 송아지 e 값을 입력 받는다.

 

2. s에서 e까지 최단 경로를 구하는 BFS 메서드를 생성한다.

 

3. 점프할 수 있는 횟수인 dis[] 배열을 생성한다.

 

4. 중복 좌표를 배제하기 위해 visited[] 배열을 생성한다. 이 때 visited[] 배열은 10000까지의 범위이므로 visited[10001]으로 초기화한다.

 

5. Queue를 LinkedList로 초기화하여 객체를 생성한다.

 

6. Q 안에 현수의 위치 값을 넣는다. (Level 0)

 

7. Q가 null 값이 아닐 때까지 루프문을 생성한다.

 

8. Q의 사이즈만큼의 루프문을 생성한다.

 

9. Q의 노드에 인접한 값 즉, Q의 첫번 째 값을 x로 만들고 x에 dis 값을 루프문을 통해 계산한 뒤(nx) 중복 값이 아니며, 1 ~ 10000까지의 범위라면 Q에 그 값을 넣는다. 만약 nx 값이 송아지 위치와 같다면 L + 1로 return 한다.

 

L + 1로 return 하는 이유는 x 값에서 dis의 거리만큼 인접한 값이 송아지 위치라는 것인데, dis 만큼 이동했다는 것은 현재의 레벨에서 다음 레벨로 이동했다는 의미이므로 L + 1로 return

 

10. 만약 해당 레벨의 Q 사이즈만큼 돌았는데 nx 값이 e와 같지 않다면 레벨을 1 증가시키고 다음 레벨에서 위 과정을 반복한다.

 

[코드]

 

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
  
public class Main {
  
  public int solution(int s, int e){
   int answer = 0;
    
    int[] dis = {1, -1, 5};
    int[] ch = new int[10001];
    
    Queue<Integer> Q = new LinkedList<>();
    
    ch[s] = 1; 
    Q.offer(s); 
   
    int L = 0;
    
    while(!Q.isEmpty()){
     
      int len = Q.size();
      
   		for(int i = 0; i < len; i++){
         int x = Q.poll();
          for(int j = 0; j < 3; j++){
           int nx = x + dis[j];
             
            if(nx == e) return L+1;
            if(nx >= 1 && nx <= 10000 && ch[nx] == 0){
             ch[nx] = 1; 
             Q.offer(nx); 
            }
         
          }
        }
      L++;
    
    }
    
    return answer;
  }
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int s = in.nextInt();
    int e = in.nextInt();
    
    System.out.println(T.solution(s,e));
  }
}