[백준/13549] 숨바꼭질3 (골드3) JAVA

package task.gold.hideandseek13549;

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int N;
    static int M;
    static Deque<Step> deque;
    static int[] visited;
    static int result;
    static final int INF_VALUE = 987654321;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        deque = new ArrayDeque<>();
        visited = new int[100000+2];
        BFS();

        System.out.println(visited[M]);
    }
    static void BFS() {
        Arrays.fill(visited, INF_VALUE);
        deque.offer(new Step(N,0));
        visited[N] = 0;

        while (!deque.isEmpty()) {
            Step poll = deque.poll();

            if (poll.pos == M) {
                result = poll.time;
                for (int i = 0; i < deque.size(); i++) {
                    Step poll1 = deque.poll();
                    if (poll1.time < result) {
                        deque.offer(poll1);
                    }
                }
                continue;
            }


            if (poll.pos - 1 >= 0) {
                if (visited[poll.pos - 1] == INF_VALUE || visited[poll.pos - 1] > poll.time + 1) {
                    visited[poll.pos - 1] = poll.time + 1;
                    deque.offer(new Step(poll.pos - 1, poll.time + 1));
                }
            }

            if (poll.pos + 1 < M + 2) {
                if (visited[poll.pos + 1] == INF_VALUE || visited[poll.pos + 1] > poll.time + 1) {
                    visited[poll.pos + 1] = poll.time + 1;
                    deque.offer(new Step(poll.pos + 1, poll.time + 1));
                }
            }

            if (poll.pos * 2 < M + 2) {
                if (visited[poll.pos * 2] == INF_VALUE || visited[poll.pos * 2] > poll.time) {
                    visited[poll.pos * 2] = poll.time;
                    deque.offer(new Step(poll.pos * 2, poll.time));
                }
            }
        }
    }

    static class Step {
        Integer pos;
        Integer time;

        public Step(Integer pos, Integer time) {
            this.pos = pos;
            this.time = time;
        }
    }
}

• max 배열의 길이 100000은 주어진 메모리상 충분히 커버가 가능함. visited로 100002짜리 배열을 선언해주고

• 하나의 경우마다 3개의 다음 경우를 만드는데 이때 적절한 제한을 두어 최대한 쓸데 없이 다음 경우를 만드는 것을 억제해야 한다.

• 다음 경우의 위치가 마이너스가 되는 경우는 필요없으므로 deque에 넣지 않는다. 다음 경우가 목표 위치의 +2 이상 될 경우도 필요 없다. +1의 경우 그 다음 -1만 해서 도달 가능하므로 +1은 봐주기.

• 또한 visited에 등록된 time값보다 다음 경우의 time이 더 작을 경우 deque에 추가하고 더 클 경우는 버린다.

• 가장 중요한 부분은 끝 처리다. M값에 도달하자마자 break을 해주는 것이 아니라 continue하여 deque의 나머지 데이터들을 모두 처리해서 최종 결과를 봐야 한다.

• M값에 도달한 time 기준으로 그 이상이 되는 time의 데이터들은 모두 필요없으므로 M값에 도달하자마자 deque를 조사하여 모두 제거해준다.(최적화 과정)