백준 [13913] 숨바꼭질 4

13913번: 숨바꼭질 4

 

 

 

Github 코드

 

 

풀이

이전 방문 지점들을 저장하고 출력하는 부분의 구현이 떠오르지 않았다. 처음 시도한 방법은 뒤, 앞, 순간이동을 통해 갈 수 있는 케이스를 클래스로 이전 노드들을 저장해가면서 구현을 해보려 했는데 모든 경우들이 다 저장되는 문제가 있었고 정확하게 최단 거리만 저장할 수 없는 문제가 있었다.

 

그래서 다른 풀이를 참고 했음. 풀이의 핵심은 다음과 같다.

• 방문을 할 때마다 이전 노드의 위치를 담을 배열을 활용
• 스택에 배열의 k 번째 노드 부터 이전 위치를 찾아가면서 스택에 담고 스택을 출력

정답 코드

package com.baekjoon.p13913;

import java.util.*;

public class Main {
    static int n, k;
    static int[] arr = new int[100001];
    static int[] before = new int[100001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        n = sc.nextInt();
        k = sc.nextInt();

        bfs();

        sb.append(arr[k] + "\n");

        Stack<Integer> s = new Stack<>();
        int i = k;
        while (i != n) {
            s.push(i);
            i = before[i];
        }
        s.push(n);

        while (!s.isEmpty()) {
            sb.append(s.pop() + " ");
        }

        System.out.println(sb);
        sc.close();
    }

    private static void bfs() {
        Queue<Integer> q = new LinkedList<>();

        q.add(n);

        while (!q.isEmpty()) {
            int now = q.poll();

            if (now == k) {
                return;
            }

            int back = now - 1;
            int front = now + 1;
            int jump = now * 2;

            if (back >= 0 && arr[back] == 0) {
                arr[back] = arr[now] + 1;
                q.add(back);
                before[back] = now;
            }
            if (front < 100001 && arr[front] == 0) {
                arr[front] = arr[now] + 1;
                q.add(front);
                before[front] = now;

            }
            if (jump < 100001 && arr[jump] == 0) {
                arr[jump] = arr[now] + 1;
                q.add(jump);
                before[jump] = now;
            }
        }

    }

}