숨바꼭질 2

너무 많이 틀린 문제입니다...

이 문제는 숨바꼭질의 변형 문제입니다. 경우의 수를 출력해야 되는 문제입니다.

저는 처음에 아주 단순하게 생각했습니다. BFS로 탐색을 하되, 목적지에 도달하는 경우 break를 하지 말고 카운트를 올리고 남은 큐를 소진하면 된다고 생각했습니다.

그러나 아무리 풀어도 해결되지 않아서 질문 게시판에서 반례를 찾아보았는데, 1 4로 입력이 주어지는 경우 2 2가 정답이라는 반례를 보게 됐습니다. 즉,

1 -> (+1)2 -> (*2)4
1 -> (*2)2 -> (*2)4

이렇게 이동하는 방법에 따라 경우의 수를 나눠야 된다는 것이었죠. 즉, 이 문제는 어떻게 움직이느냐가 중요하지, 어떤 위치로 움직였느냐를 세는 문제가 아니었습니다. (왜때문에...)

따라서 여러 번의 삽질 끝에 다음과 같은 사실을 깨닫게 되었습니다.

• 최단시간으로 목적지에 도착하는 경우를 생각했을 때, 1초전에 있을 수 있는 위치는 목적지-1, 목적지/2, 목적지+1 이다.
• 이 각 목적지는 최단시간-1초 여야 한다.
• 따라서, 위치에 방문 여부만 체크할 것이 아니라 몇 초에 도달했는지를 체크한다.
• 해당 위치에 도달하는 또 다른 상태(BFS탐색시 큐에 들어가는 상태)가 있을 때, 시간이 같다면 그 상태 역시 사용(해당 상태에서 +1, -1, *2 위치를 큐에 넣는다)한다.

정답

package bj.comito.codeplus.practice;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class BJ12851 {
    private static int N;
    private static int K;
    private static final int[] visited = new int[200_001];

    public static void main(String[] args) throws Throwable {
        final Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();

        sc.close();

        Arrays.fill(visited, -1);

        solve();
    }

    private static void solve() {
        // N >= K의 경우, 경우의 수는 1이고
        // 시간 값은 N - K이다.
        // 같은 지점인 경우 0초가 걸리고
        // N이 뒤로밖에 못 움직이는 경우에는
        // N - K 만큼의 시간이 걸리기 떄문이다.
        if (N >= K) {
            System.out.println(N - K);
            System.out.println(1);
            return;
        }

        Deque<State> q = new LinkedList<>();

        q.offer(new State(N, 0));
        // 시작 지점의 방문 시간은 0이다.
        visited[N] = 0;

        int time = Integer.MAX_VALUE;
        int count = 0;
        while (!q.isEmpty()) {
            State cur = q.poll();

            // BFS이므로
            // 상태의 시간이 최단시간보다 커졌다면
            // 그 이후는 볼 필요가 없다.
            if (cur.time > time) {
                break;
            }

            // 정답의 경우
            if (cur.position == K) {
                time = cur.time;
                count++;
                continue;
            }

            State next;

            next = cur.back();
            if (next != null) {
                q.offer(next);
                next.checkVisit();
            }

            next = cur.front();
            if (next != null) {
                q.offer(next);
                next.checkVisit();
            }

            next = cur.teleport();
            if (next != null) {
                q.offer(next);
                next.checkVisit();
            }
        }

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

    static class State {
        final int time;
        final int position;

        public State(int position, int time) {
            this.position = position;
            this.time = time;
        }

        public State back() {
            final int pos = position - 1;
            final int nextTime = time + 1;

            if (!canVisit(pos, nextTime)) {
                return null;
            }

            return new State(pos, nextTime);
        }

        public State front() {
            final int pos = position + 1;
            final int nextTime = time + 1;
            if (!canVisit(pos, nextTime)) {
                return null;
            }

            return new State(pos, nextTime);
        }

        public State teleport() {
            final int pos = position * 2;
            final int nextTime = time + 1;

            if (!canVisit(pos, nextTime)) {
                return null;
            }

            return new State(pos, nextTime);
        }

        public static boolean canVisit(int pos, int time) {
            if (isOutOfIndex(pos)) {
                return false;
            }

            // 처음 방문하면 무조건 방문 가능
            if (visited[pos] == -1) {
                return true;
            }

            // 이미 방문한 지점이면 같은 시간이여야만 방문 가능
            return visited[pos] == time;
        }

        public void checkVisit() {
            visited[position] = time;
        }

        private static boolean isOutOfIndex(int pos) {
            return pos < 0 || pos > 200_000;
        }
    }
}