[TIL] 백준 골드5 숨바꼭질3

https://www.acmicpc.net/problem/13549
백준 골드5 숨바꼭질3

오랜만에 보는 탐색문제.
다 까먹었지만 이 문제는 꽤 많이 본 유형이라 BFS라는 것을 바로 떠올렸다.

접한지 오래 되긴 했지만 점점 생각해보며 풀이를 구상하였다.

그래프는 위 사진과 같은 모양이 된다.
x-1, x+1, 2x의 경우를 생각해주어야 하기 때문.

하지만 막힌 부분이 있었다.
시간을 어떻게 담지?

2x는 순간이동 취급이라 0초가 걸리고
x+1, x-1는 걷는 것이라 1초가 걸린다.

이는 Node 클래스를 사용해 위치에 따른 시간 정보를 담아 객체를 만들어주었다.

하지만 반례는 다 성공하는데 제출하면 실패가 떴다.
이유가 뭔가 하여 더 찾아보았더니
x-1과 x+1의 순서에 따라 답이 달라진다고...
x-1을 더 먼저 해야된다고 한다.
2x는 시간이 더 적게 걸리는만큼 우선순위인 것은 알았는데
x-1과 x+1의 순서가 중요했을 줄이야

x-1, x+1의 순서에 관하여 아래의 링크를 참고하였다.
https://www.acmicpc.net/board/view/104177

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String str = bufferedReader.readLine();
        int N = Integer.parseInt(str.split(" ")[0]);
        int K = Integer.parseInt(str.split(" ")[1]);
        int visit[] = new int[100001];

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(N, 0));
        visit[N] = 1;
        int time = Integer.MAX_VALUE;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            if(node.x == K){
                time = Math.min(time, node.time);
            }

            if(node.x * 2 <= 100000 && visit[node.x * 2] == 0) //방문 안한거
            {
                queue.add(new Node(2 * node.x, node.time));
                visit[node.x * 2] = 1;
            }

            if(node.x - 1 >= 0 && visit[node.x - 1] == 0){
                queue.add(new Node(node.x - 1, node.time + 1));
                visit[node.x - 1] = 1;
            }

            if(node.x + 1 <= 100000 && visit[node.x + 1] == 0){
                queue.add(new Node(node.x + 1, node.time + 1));
                visit[node.x + 1] = 1;
            }

        }
        System.out.println(time);
    }
}

class Node{
    int x, time;

    Node(int x, int time){
        this.x = x;
        this.time = time;
    }
}