[BFS] 송아지 찾기

BFS(너비 우선 탐색)를 활용한 송아지 찾기 문제를 풀어본다. 이 문제는 수빈이가 동생 송아지를 찾기 위해 이동하는 최단 거리를 구하는 문제다. 수빈이는 현재 위치에서 1칸 앞, 1칸 뒤, 5칸 앞의 세 가지 이동 옵션을 가질 수 있다. 주어진 출발지에서 목적지까지 도달하는 가장 빠른 방법을 BFS로 찾는 과정이다.

 

문제 설명

• 수빈이가 현재 있는 위치 s에서 동생 송아지가 있는 위치 e까지 최단 경로를 찾아야 한다.
• 수빈이는 매번 1칸 앞으로, 1칸 뒤로, 또는 5칸 앞으로 이동할 수 있다.
• 수빈이가 송아지에게 도달하는 최소 이동 횟수를 출력하는 문제이다.

해결 방법

이 문제는 최단 거리를 찾는 문제이므로 BFS를 사용하는 것이 적합하다. BFS는 각 단계에서 가능한 모든 경로를 탐색하면서 최단 경로를 찾기 때문에, 이동할 수 있는 세 가지 옵션을 모두 고려해 각 단계에서 새로운 위치로 이동하도록 구현하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    int answer = 0;
    int[] dis = {1, -1, 5}; // 1칸 앞, 1칸 뒤, 5칸 앞의 이동 범위
    int[] ch; // 방문 체크 배열

    Queue<Integer> queue = new LinkedList<>(); // BFS를 위한 큐
    public int BFS(int s, int e) {
        ch = new int[10001]; // 범위가 1부터 10000까지
        ch[s] = 1; // 시작점 방문 처리
        queue.offer(s); // 시작점을 큐에 넣음
        int L = 0; // BFS 레벨 (이동 횟수)

        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int x = queue.poll(); // 현재 위치
                for (int j = 0; j < 3; j++) { // 3가지 이동 옵션을 확인
                    int nx = x + dis[j]; // 새로운 위치 계산
                    if (nx == e) { // 목적지에 도달하면
                        return L + 1; // 최단 거리 리턴
                    }
                    if (nx >= 1 && nx <= 10000 && ch[nx] == 0) { // 유효한 범위 내에서 아직 방문하지 않은 위치라면
                        ch[nx] = 1; // 방문 처리
                        queue.offer(nx); // 큐에 새로운 위치 추가
                    }
                }
            }
            L++; // 레벨 증가 (한 번의 이동 완료)
        }
        return 0; // 목적지에 도달하지 못했을 때 (실패)
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        int a = Integer.parseInt(str[0]); // 시작 위치
        int b = Integer.parseInt(str[1]); // 목표 위치

        Main T = new Main();

        System.out.println(T.BFS(a, b)); // 결과 출력
    }
}

주요 로직 설명

• dis[] 배열을 통해 수빈이가 이동할 수 있는 1칸 앞, 1칸 뒤, 5칸 앞의 옵션을 정의하였다.
• BFS 메서드는 수빈이의 시작점에서 BFS를 수행하여 목적지까지의 최단 거리를 계산한다.
• 각 위치는 방문 체크 배열 ch[]를 통해 한 번만 방문하도록 하여 무한 루프를 방지하였다.
• queue를 사용하여 현재 위치에서 이동 가능한 모든 경우를 탐색하면서 최단 경로를 찾는다.

핵심 포인트

BFS는 각 단계에서 모든 가능한 경로를 동시에 고려하기 때문에 최단 경로를 보장한다. 따라서 송아지 찾기 문제와 같이 최단 거리를 구하는 문제에서는 BFS가 적합한 알고리즘이다.

 

시간 복잡도

탐색할 수 있는 최대 범위는 1부터 10000까지이며, BFS는 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(N)이다.