백준-13913번/숨바꼭질 4(java)

 

문제 이해

 

1697번 문제 숨바꼭질과 비슷한 문제이지만, 요구사항이 하나 더 추가 되었다.

https://developerwoohyeon.tistory.com/114

백준-1697번/숨바꼭질(java)

 

 

추가된 요구사항 : 목적지 까지의 최소 이동시간이 소요되는 경로를 순서대로 출력

 

경로를 순서대로 출력하기 위해서는 배열이 하나 더 추가되어야 한다.

 

static int[] arr = new int[100001];
static int[] time = new int[100001];

 

time ==> 이동하는데 걸린 시간 기록

arr ==> 해당 위치에 도달하기 전에 방문한 위치를 기록

 

arr을 이용하면 이동경로의 역순을 구할 수 있다.

 

문제 해결

 

Stack<Integer> stack = new Stack<>();
stack.push(point);
int index = point;

while(index!=now){
    stack.push(arr[index]);
    index=arr[index];
}

 

동생의 위치를 stack에 push 해준다.

 

그 후, arr에는 현 위치를 방문하기 전의 위치가 저장되어 있으므로 , stack에 arr[현위치]를 추가해주면서 index가 수빈이의 첫 위치와 같아 질때까지 반복해준다.

 

stack에는 위치가 역순으로 push되어 있으므로 stack 구조상 pop을 stack이 비어 있을때 까지 해주면 이동경로를 순서대로 출력할 수 있다.

 

<전체 코드>

import java.util.*;

public class Problem13913 {

    static int[] arr = new int[100001];
    static int[] time = new int[100001];
    static boolean[] visit = new boolean[100001];
    static int[] move = {1,-1,2};

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

        int now = scanner.nextInt();;
        int point = scanner.nextInt();
        Arrays.fill(arr,0);
        BFS(now);

        Stack<Integer> stack = new Stack<>();
        stack.push(point);
        int index = point;

        while(index!=now){
            stack.push(arr[index]);
            index=arr[index];
        }

        System.out.println(time[point]);
        while(!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
    }

    public static void BFS(int now){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(now);
        visit[now]=true;

        while(!queue.isEmpty()){
            int point = queue.poll();
            for(int i=0; i<3; i++){
                if(i==2){
                    int next = point*2;
                    if(next<0 || next>100000){
                        continue;
                    }
                    if(visit[next]){
                        continue;
                    }
                    queue.add(next);
                    time[next]=time[point]+1;
                    visit[next]=true;
                    arr[next]=point;

                }
                else {
                    int next = point + move[i];
                    if(next<0 || next>100000){
                        continue;
                    }
                    if(visit[next]){
                        continue;
                    }
                    queue.add(next);
                    time[next]=time[point]+1;
                    visit[next]=true;
                    arr[next]=point;
                }
            }
        }
    }
}