✍ 문제

문제링크

문제

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

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

입력

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

출력

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

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

👏 풀이과정

그냥 dfs 로 풀면 풀리지 않는 문제이다.
queue에 넣을때 방문처리를 하지 않고, queue에서 꺼낼때 방문처리하면 되는 문제이다.

꺼낸 노드중에 +1, -1 ,2 가 방문처리안되있으면 queue에 담아준다.
그리고 꺼낼때 방문처리를 해주고, pool한 노드가 K이면 같은 cost를 한 사이클 돌리고 while문을 중지시킨다.
(꺼낼때 방문처리를 해주는 이유는 중복해서 방문할 수 있기 때문이다. 같은 코스트를 가지는 노드는 queue에 다 들어가기 때문에 모든 경우의 수를 알아낼 수 있다. 다른 cost를 가지면 queue에 들어가지 않기 때문에 시간을 많이 잡아먹지 않는다...)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


// 중복해서 갈 수 있다.
public class Main {
    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());
        int K = Integer.parseInt(st.nextToken());

        Boolean[] visited = new Boolean[100001];
        for (int i = 0 ; i < visited.length ;i++){
            visited[i] = false;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(N, 0));
        int count = 0;
        int cost = 100000;
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            visited[poll.n] = true;
            if (cost < poll.cost) {
                break;
            }
            if (poll.n == K ) {
                count++;
                cost = poll.cost;
            }



            if (poll.n + 1 > -1 && poll.n + 1 < 100001) {
                if (visited[poll.n + 1] == false) {

                    queue.add(new Node(poll.n + 1, poll.cost + 1));

                }

            }if (poll.n -1 > -1 && poll.n -1 < 100001) {
                if (visited[poll.n - 1] == false) {

                    queue.add(new Node(poll.n -1, poll.cost + 1));
                }

            }
            if (poll.n*2 > -1 && poll.n*2 < 100001) {
                if(visited[poll.n * 2] == false){

                    queue.add(new Node(poll.n *2, poll.cost + 1));
                }

            }

        }
//        가장 빠른시간...?

        System.out.println(cost);
        System.out.println(count);
    }

    static class Node{
        int n;
        int cost;

        Node(int n, int cost) {
            this.n=n;
            this.cost = cost;

        }
    }
}