13913 : 숨바꼭질 4 Java

13913번: 숨바꼭질 4

처음에는 Move 클래스 안에 StringBuilder나 StringBuffer를 넣어서 이전의 경로를 복사해서 최종 경로를 찍도록 했는데 시간 초과가 났다. 아무래도 복사 비용과 새 인스턴스 생성하는 비용이 커서 그런 것 같다.

그래서 예전에 봤던 방법을 사용했는데 prev 배열에 직전 경로를 저장하는 방법이다.
prev[a] = b 는 a로 가기위해서는 b를 거친다는 의미이다. 이후 아래와 같이 마지막 K부터 시작점 N까지의 경로를 추적해서 출력하면 된다.

int index = K;
while(index != N){
    index = prev[index];
}

방문 처리 위치에 따라 직전 경로가 갱신이 될 수 있기 때문에 방문 처리 위치도 중요하다.

static void BFS() throws IOException {
    while (!q.isEmpty()) {
        Move current = q.poll();
        if (current.now == K) {
            bw.write(current.time + "\n");
            return;
        }
        if(v[current.now]){
            continue;
        }
        v[current.now] = true; // 현재 노드가 큐에서 poll되어야만 방문처리

        for (int next : new int[]{current.now - 1, current.now + 1, current.now * 2}) {
            if (next < 0 || next >= MAX || v[next]) {
                continue;
            }
            q.add(new Move(next, current.time + 1));
            prev[next] = current.now; // 자식 노드가 겹칠 경우 여러 번 갱신될 수 있다.
        }
    }
}

본인은 위와 같이 방문 처리를 큐에서 노드를 꺼낼 때 했었는데 여기서 문제가 생겼다. 해당 노드가 poll되었을 때 방문 처리하게 되면 자식 노드가 겹칠 때 여러 번 갱신될 수 있다.

쉽게 예제로 확인해보자.
q = [] // 현재 위치와 시간 와 같이 큐와
v = [false, false, false, false, false, false, false, …]방문을 처리할 배열이 있다고 하자.

 

q = [{3, 0}]
큐에서 {3, 0}이 poll된다.
v = [false, false, false, true, false, false, false, …]
3번을 방문 처리하고, 방문 가능한 노드들을 삽입한다.
prev[2] = 3, prev[4] = 3, prev[6] = 3으로 갱신되고 차례로 2번, 4번, 6번이 삽입된다.

 

q = [{2, 1}, {4, 1}, {6, 1}]
다시 큐에서 {2, 1}이 poll된다.
v = [false, false, true, true, false, false, false, …]
2번을 방문 처리하고, 방문 가능한 노드들을 삽입한다.
이미 3번 노드는 방문 처리를 했기 때문에 prev[1] = 2, prev[4] = 2로 갱신되고 차례로 1번, 4번이 삽입된다.

 

q = [{4, 1}, {6, 1}, {1, 2}, {4,1}]
4번 노드는 이제서야 방문처리하게 된다.
v = [false, false, true, true, true, false, false, …]
4번 노드는 이미 한 번 경로를 갱신 했지만, 실제로 방문 처리하기 전에 자식이 겹쳐 다시 직전 경로가 갱신되고 말았다.
따라서, 딱 한 번만 직전 경로를 갱신하기 위해서는 자식을 검사할 때 방문처리를 해야 한다.

for(int next : new int[]{현재 좌표 - 1, 현재 좌표 + 1, 현재 좌표 * 2}){
    v[다음 좌표] = true;
}

그리고 출력의 경우 K부터 N까지 역추적하므로 Stack을 사용했다.

전체 코드

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class Main {
    static final int MAX = 100_001;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static boolean[] v = new boolean[MAX];

    static int[] prev = new int[MAX];

    static class Move {
        int now;
        int time;

        public Move(int now, int time) {
            this.now = now;
            this.time = time;
        }

    }

    static Stack<Integer> s = new Stack<>();
    static Queue<Move> q = new ArrayDeque<>();
    static int N, K;

    public static void main(String[] args) throws IOException {
//        System.setIn(Files.newInputStream(Paths.get("src/input.txt")));
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        prev[N] = N;
        q.add(new Move(N, 0));
        BFS();
        int idx = prev[K];
        s.add(K);
        while (idx != N){
            s.add(idx);
            idx = prev[idx];
        }
        if(N != K){
            s.add(N);
        }
        while (!s.isEmpty()) {
            bw.write(s.pop() + " ");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void BFS() throws IOException {
        while (!q.isEmpty()) {
            Move current = q.poll();
            if (current.now == K) {
                bw.write(current.time + "\n");
                return;
            }
            for (int next : new int[]{current.now - 1, current.now + 1, current.now * 2}) {
                if (next < 0 || next >= MAX || v[next]) {
                    continue;
                }
                v[next] = true; // 이부분 때문에 달라짐 -> 여기서 방문 처리를 하기 때문에 단 한 번만 방문을 보장함.
                q.add(new Move(next, current.time + 1));
                prev[next] = current.now; // 갱신 딱 한 번만 되는 것을 보장한다.
            }
        }
    }

}