백준 13549번 : 숨바꼭질 3 (자바, 반례모음)

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

---

문제

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

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

---

입력

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

---

출력

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

🔵풀이

맞왜틀을 계속 외쳤던 문제였습니다... 많은 고생을 한 만큼 반례도 남기도록 하겠습니다. 저같은 경우 우선순위 큐+ bfs로 풀이하였습니다. 근데 수빈이의 위치를 옮기는 경우마다 조건이 달라져 많이 틀렸습니다..(처음에 잘 생각하여 조건문을 작성해보시길 추천합니다.)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
    int x = Integer.valueOf(stringTokenizer.nextToken());
    int n = Integer.valueOf(stringTokenizer.nextToken());
    boolean[] visit = new boolean[100001];
    PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return o1[1]-o2[1];
      }
    });

    int tmp = x;
    int count = 0;
    visit[x] = true;
    queue.add(new int[]{x,0});

    while (tmp!=n) {
      tmp = queue.peek()[0];
      count = queue.peek()[1];
      queue.poll();
      visit[tmp] = true;

      if (tmp>0&&!visit[tmp-1]){
        queue.add(new int[]{tmp - 1, count + 1});
      }
      if (tmp<100000&&!visit[tmp+1]) {
        queue.add(new int[]{tmp + 1, count + 1});
      }
      if (tmp<n&&tmp!=0&&tmp*2<=100000) {
        queue.add(new int[]{tmp * 2, count});
      }
    }

    System.out.println(count);
  }
}