링크

13913. 숨바꼭질 4

문제

풀이

이 문제는 N에서 K로 가는 길과 시간을 출력하는 것이 문제이다.
시간은 쉽지만 길은 어려웠다.
처음에 모든 길을 저장했었는데 메모리가 초과되었다.
그래서 조언받은 방법이 이동을 기록할 배열을 하나 만들고 기록하는 방법이다.
그 배열에 다음 인덱스에 = 현재 인덱스를 저장했다.

			for(int i=0;i<3;i++){
                int newLocation = 0;

                // +1
                if(i == 0){
                    newLocation = location + 1;
                }
                // -1
                else if(i == 1){
                    newLocation = location - 1;
                }
                // *2
                else{
                    newLocation = location * 2;
                }

                if(newLocation < 0 || newLocation >= visited.length) continue;

                if(visited[newLocation]) continue;
                visited[newLocation] = true;

                load[newLocation] = location;

//                System.out.println("currentLocation = " + newLocation);
//                for(int l=0;l<=k;l++){
//                    System.out.print(load[l] + " ");
//                }
//                System.out.println();

                queue.add(new Node(newLocation, time+1));

            }

이렇게 방문하지 않았으면 load라는 배열에다가 이동한 인덱스에 현재 위치를 넣어줬다. 이렇게 하면 인풋이 4 7일때

load[7] = 8, 8번째 인덱스를 타고 load[8]은 4를 가리키고 load[4] = 0 이므로 도착한 것을 의미한다.
그래서 stack에 인덱스값을 순차적으로 넣었다.

코드

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

class Node{
    int location;
    int time;

    public Node(int location, int time){
        this.location = location;
        this.time = time;
    }

}

public class Main {
    public static Stack<Integer> stack = new Stack<>();

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

        String[] arr = br.readLine().split(" ");

        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);

        boolean[] visited = new boolean[100001];
        int[] load = new int[100001];

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, 0));
        load[n] = 0;
        visited[n] = true;

        int answer = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();

            int location = node.location;
            int time = node.time;

            if(location == k){
                answer = time;
                break;
            }

            for(int i=0;i<3;i++){
                int newLocation = 0;

                // +1
                if(i == 0){
                    newLocation = location + 1;
                }
                // -1
                else if(i == 1){
                    newLocation = location - 1;
                }
                // *2
                else{
                    newLocation = location * 2;
                }

                if(newLocation < 0 || newLocation >= visited.length) continue;

                if(visited[newLocation]) continue;
                visited[newLocation] = true;

                load[newLocation] = location;

//                System.out.println("currentLocation = " + newLocation);
//                for(int l=0;l<=k;l++){
//                    System.out.print(load[l] + " ");
//                }
//                System.out.println();

                queue.add(new Node(newLocation, time+1));

            }


        }
//        System.out.println(Arrays.toString(load));

        int pivot = k;
        while(true){
            stack.push(pivot);

            if(load[pivot] == 0){
                if(n == 0 && pivot != 0){
                    stack.push(0);
                }
                break;
            }

            pivot = load[pivot];

        }


        System.out.println(answer);
        while(!stack.isEmpty()){
            System.out.print(stack.pop() + " ");
        }

    }

}