[백준/Java] 13913번 숨바꼭질 4

-Code

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

public class BOJ13913 {
    static class Info {
        int pos, time;

        public Info(int pos, int time) {
            this.pos = pos;
            this.time = time;
        }
    }
    static Integer[] parents = new Integer[100001];
    static {
        Arrays.fill(parents, null);
    }

    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());
        // 탐색 로직
        Info answer = getInfo(new Info(subinPos, 0), sisterPos);
        // 출력
        StringBuilder sb = new StringBuilder();
        sb.append(answer.time).append("\n");
        // 역추적
        ArrayList<Integer> posList = new ArrayList<>();
        int pos = sisterPos;
        while (pos != -1) {
            posList.add(pos);
            pos = parents[pos];
        }
        // 역추적
        Collections.reverse(posList); // 11 버전이므로 변경
        for (int p : posList) {
            sb.append(p).append(" ");
        }
        System.out.println(sb);
        
    }

    private static Info getInfo(Info subin, int target) {
        // visited 셋팅
        parents[subin.pos] = -1;
        // 덱 셋팅
        Deque<Info> infoDeq = new ArrayDeque<>();
        infoDeq.addLast(subin);
        // 탐색
        while (!infoDeq.isEmpty()) {
            Info now = infoDeq.pollFirst();

            if (now.pos == target) {
                return now;
            }
            // 이동 위치 배열
            int[] movePos = {now.pos - 1, now.pos + 1, now.pos * 2};
            for (int next : movePos) {
                // 움직일 수 있고 방문하지 않은 경우
                if (isMove(next) && parents[next] == null) {
                    // 해당 위치에 부모 위치를 넣어서 추적 가능하도록함
                    parents[next] = now.pos;
                    infoDeq.addLast(new Info(next, now.time + 1));
                }
            }
        }
        return null;
    }

    private static boolean isMove(int next) {
        return (next >= 0 && next < 100001);
    }
}

처음에 ArrayList를 class에 넣어서 이동한 곳을 추적하려 했으나 메모리 초과 발생할 수 있다는 것을 알게 되었습니다. 그래서 힌트로 얻은 게 배열 하나에 현재 위치를 인덱스로 하고 그 위치에 이전 위치를 담아서 도착점부터 역방향으로 돌면서 추적은 것이었습니다. 해당 방법을 Integer로 null이 가능하게 받아서 시작점을 -1로 하고 방문하지 않은 곳을 null로 하여 검사해 해결했습니다.