백준 13549 [자바] java 숨바꼭질 3

문제 링크: https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

▶ 문제  숨바꼭질 3

---

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

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

 

▶ 입력

---

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

▶ 해설

 

---

수빈이와 동생의 위치를 같게 하는데 움직일 수 있는 조건이 3가지 이다. 그래서 처음에 dfs로 풀이를 하였지만 StackOverflow가 발생해서 bfs로 수정했습니다. 수빈이가 움직이면서 3가지 조건만 확인해주면 된다. 수빈이의 위치를 X라고 가정합니다. 

1.  X*2 <=100001

2.  X+1 <= 100001

3.  X-1 >=0

위 3가지 조건을 충족하며 수빈이가 이미 들린 곳들을 체크하면서 bfs 접근을 했습니다. 

import java.util.*;
import java.io.*;
 
class Node{
    int where;
    int time;
 
    public Node(int where, int time) {
        this.where = where;
        this.time = time;
    }
}
 
public class Main {
    static int n,k;
    static boolean [] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n= Integer.parseInt(s[0]);
        k = Integer.parseInt(s[1]);
        check= new boolean[100002];
        solve();
    }
 
    public static void solve(){
        Queue<Node> queue =new ArrayDeque<>();
        queue.add(new Node(n, 0));
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            if(poll.where==k){
                System.out.println(poll.time);
                return;
            }
 
            if(poll.where*2<=100001 && !check[poll.where*2]){
                queue.add(new Node(poll.where*2, poll.time));
                check[poll.where*2]=true;
            }
            if(poll.where-1>=0 &&!check[poll.where-1]){
                queue.add(new Node(poll.where-1, poll.time+1));
                check[poll.where-1]=true;
            }
            if(poll.where+1<=100001 && !check[poll.where+1]){
                queue.add(new Node(poll.where+1, poll.time+1));
                check[poll.where+1]=true;
            }
        }
    }
}