[1697] 숨바꼭질

🔗 문제 링크

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는 정수이다.

🗝 풀이 (언어 : Java)

BFS로 풀었다. 중요한 포인트는 시간이 갈수록 해당 시간초마다 경우의 수가 다르며, 계속 증가하는데 이것을 같은 시간끼리 묶어주려면 큐의 크기 단위로 같은 시간대의 가능한 지점들로 생각하면 된다. 방문 처리 배열도 조건상 100000까지 이므로 2배까지 가능하니까 200000 값까지 수용할 수 있는 범위로 만들어주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    private int findMinSeconds(int n, int m) {
        // n과 m이 같은 지점일 경우 예외 처리
        if (n == m)
            return 0;
        int time = 0;
        boolean[] visited = new boolean[200001]; // 0~200000까지 가능
        Queue<Integer> queue = new LinkedList<>();
        queue.add(n-1);
        queue.add(n+1);
        queue.add(n*2);
        // BFS
        while(!queue.isEmpty()) {
            time++; // 1초 증가
            int size = queue.size(); // 큐의 크기만큼의 원소들이 같은 시간초 시점
            for (int i = 0; i < size; i++) {
                int point = queue.poll();
                if (point == m) // 목표 지점 도달 시간초 반환
                    return time;
                // 조건상 불가능한 범위, 이미 방문했던 지점이면 스킵
                if (point < 0 || point > 200000 || visited[point])
                    continue;
                visited[point] = true; // 현 지점 방문 처리
                queue.add(point-1);
                queue.add(point+1);
                queue.add(point*2);
            }
        }
        return 0; // 여기는 올일이 없는 return
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
        br.close();
        System.out.print(new Main().findMinSeconds(n, m));
    }
}