[백준] CLASS3 1697 숨바꼭질 - JAVA [자바]

안녕하세요. 이번에는 백준 1697 숨바꼭질 문제를 풀어보려고 합니다.

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

1697번: 숨바꼭질

---

 

Problem

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

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

사진 1. 문제

---

Solution

import java.io.*;
import java.util.*;

public class Main {
    
    static int N, K;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        
        N = Integer.parseInt(arr[0]);
        K = Integer.parseInt(arr[1]);
        
        if(N == K) {
            System.out.println(0);
        } else {
            bfs(N);
        }
    }
    
    public static void bfs(int n) {
        // 범위가 (0 ≤ N ≤ 100,000) 이기 때문에 100001
        boolean[] visited = new boolean[100001];
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(n);
        int size = q.size();
        int count = 0;
        
        while(true) {
            count++;
            size = q.size();
            
            for(int i = 0; i < size; i++) {
                int x = q.poll();
                visited[x] = true;
            
                if(x - 1 == K || x + 1 == K || x * 2 == K) {
                    System.out.println(count);
                    return;
                } 
            
                if(x - 1 > 0 && !visited[x - 1]) {
                    q.offer(x - 1);
                    visited[x - 1] = true;
                }
            
                if(x + 1 < 100001 && !visited[x + 1]) {
                    q.offer(x + 1);
                    visited[x + 1] = true;
                }
            
                if(x * 2 < 100001 && !visited[x * 2]) {
                    q.offer(x * 2);
                    visited[x * 2] = true;
                }
            }    
        }   
    }
}

---

Performance

사진 2. 실행 결과