[99클럽 5기 코테 스터디 TIL 7일차] 숨바꼭질 (feat. 너비 우선 탐색(BFS))

1) 문제

https://www.acmicpc.net/problem/1697

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

 

 

2) 문제풀이

• 너비 우선 탐색(BFS)를 이용하여 해결 가능
• BFS는 최단 경로를 찾는 데 유용한 알고리즘
• 동생을 찾는 가장 빠른 시간을 구하는 데 적합
• BFS를 통해 현재 위치에서 가능한 모든 이동을 탐색하며, 동생을 찾는 최단 시간을 구함

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 받기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력을 위한 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력 파싱
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]); // 수빈이 위치
        int K = Integer.parseInt(input[1]); // 동생 위치

        // BFS를 통해 최단 시간 계산
        int result = bfs(N, K);

        // 결과 출력
        bw.write(result + "\n");
        bw.flush();

        // 스트림 닫기
        br.close();
        bw.close();
    }

    public static int bfs(int start, int target) {
        // 방문 여부 확인 배열 (최대 범위는 문제에서 100,000으로 제한)
        boolean[] visited = new boolean[100001];
        // BFS 탐색을 위한 큐
        Queue<int[]> queue = new LinkedList<>();

        // 시작 위치를 큐에 추가 (위치와 시간 정보를 저장)
        queue.add(new int[]{start, 0});
        visited[start] = true;

        // BFS 수행
        while (!queue.isEmpty()) {
            // 현재 위치와 시간 정보 꺼내기
            int[] current = queue.poll();
            int position = current[0];
            int time = current[1];

            // 동생의 위치에 도달하면 시간을 반환
            if (position == target) {
                return time;
            }

            // 가능한 이동 위치 탐색
            int[] nextPositions = {position - 1, position + 1, position * 2};
            for (int next : nextPositions) {
                // 이동 가능한 범위 내에서 아직 방문하지 않은 위치라면
                if (next >= 0 && next <= 100000 && !visited[next]) {
                    queue.add(new int[]{next, time + 1}); // 큐에 추가
                    visited[next] = true; // 방문 처리
                }
            }
        }

        // 논리적으로 이 코드에 도달할 일은 없음 (문제에서 항상 답이 존재한다고 가정)
        return -1;
    }
}

 

3) 세부 설명

1. 입력 처리
   • 수빈이의 위치 N과 동생의 위치 K를 입력으로 받음
   • 최대 범위가 100,000이므로 이를 활용해 탐색 범위를 제한함
2. 방문 여부 확인
   • boolean[] visited 배열로 각 위치가 방문되었는지 확인함
   • 이는 중복 방문을 방지하고 탐색 속도를 높임
3. BFS 탐색 준비
   • Queue<int[]>는 현재 위치와 이동 시간을 저장함
   • 초기값으로 수빈이의 시작 위치와 시간(0초)을 큐에 추가하고, 방문 처리함
4. BFS 탐색
   • 큐에서 위치와 시간을 꺼내어 현재 위치가 동생의 위치와 같은지 확인함
   • 같다면 현재 시간을 반환
   • 현재 위치에서 가능한 이동(1초 후 X-1, X+1, 2*X)을 계산하고, 유효한 위치라면 큐에 추가
5. 최단 시간 계산
   • BFS는 탐색 순서대로 최단 경로를 보장하기 때문에 동생의 위치에 처음 도달하는 시간이 가장 빠른 시간임
6. 결과 반환
   • 동생의 위치에 도달한 시간을 반환함