[백준/Java] 13549번 숨바꼭질 3

-Code

import java.io.*;
import java.util.*;

public class BOJ13549 {
    static class Pos {
        int x, time;

        public Pos (int x, int time) {
            this.x = x;
            this.time = time;
        }
    }
    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int subinPos = Integer.parseInt(st.nextToken());
        int sisterPos = Integer.parseInt(st.nextToken());

        System.out.println(getMinTime(new Pos(subinPos, 0), sisterPos));
    }

    private static int getMinTime(Pos subinPos, int target) {
        visited[subinPos.x] = true;
        Deque<Pos> posDeq = new ArrayDeque<>();
        posDeq.addLast(subinPos);

        while (!posDeq.isEmpty()) {
            Pos now = posDeq.pollFirst();

            if (now.x == target) {
                return now.time;
            }

            int[] nextList = {now.x * 2, now.x - 1, now.x + 1};
            for (int i = 0; i < 3; i++) {
                int next = nextList[i];
                if (isMove(next) && !visited[next]) {
                    int tempTime = now.time + (i == 0 ? 0 : 1);
                    posDeq.addLast(new Pos(next, tempTime));
                    visited[next] = true;
                }
            }
        }
        return 0;
    }

    private static boolean isMove(int p) {
        return (0 <= p && p <= 100000);
    }
}

처음에 이렇게 해서 맞았는데 찾아보니 모든 입력에 맞는 코드가 아니라고 합니다. 아래와 같이 곱하기 2로 이동하는 것이 시간을 쓰지 않는 가중치를 가지기 때문에 이를 덱에 맨 앞으로 넣어서 검사를 해야 정확한 값을 반환할 수 있다고 합니다.

import java.io.*;
import java.util.*;

public class BOJ13549 {
    static class Pos {
        int x, time;

        public Pos (int x, int time) {
            this.x = x;
            this.time = time;
        }
    }
    static boolean[] visited = new boolean[100001];

    public static void main(String[] args) throws Exception {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int subinPos = Integer.parseInt(st.nextToken());
        int sisterPos = Integer.parseInt(st.nextToken());

        System.out.println(getMinTime(new Pos(subinPos, 0), sisterPos));
    }

    private static int getMinTime(Pos subinPos, int target) {
        visited[subinPos.x] = true;
        Deque<Pos> posDeq = new ArrayDeque<>();
        posDeq.addLast(subinPos);

        while (!posDeq.isEmpty()) {
            Pos now = posDeq.pollFirst();

            if (now.x == target) {
                return now.time;
            }

            int[] nextList = {now.x * 2, now.x - 1, now.x + 1};
            for (int i = 0; i < 3; i++) {
                int next = nextList[i];
                if (isMove(next) && !visited[next]) {
                    if (i == 0) {
                        posDeq.addFirst(new Pos(next, now.time));
                    } else {
                        posDeq.addLast(new Pos(next, now.time + 1));
                    }
                    visited[next] = true;
                }
            }
        }
        return 0;
    }

    private static boolean isMove(int p) {
        return (0 <= p && p <= 100000);
    }
}