[백준] 13913번 숨바꼭질4 문제 풀어보기 (이동기록 역순으로 출력하는 법)
1. 문제
1) 링크
2) 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
3) 입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
4) 출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
더 자세한 문제의 조건을 보고 싶으면 위의 링크를 클릭해 백준 사이트로 들어가보자
2. 유사한 백준 문제
이 문제와 유사한 숨바꼭질 문제를 이전 포스팅에서 다룬 바 있다.
https://www.programmingstory.com/2024/03/1697-bfs.html
위의 문제와 다른 점은 위 문제는 빠른 시간만 출력을 하는 문제이고 이번 문제는 가장 빠른 시간의 이동 기록도 모두 출력하는 문제라는 점이다.
따라서 빠른 시간 출력하는 부분은 위의 포스팅에서 다루었으므로 따로 설명을 안하고 어떻게 이동기록을 역순으로 출력할 수 있는지에 대해서 생각해보겠다.
3. 풀이
BFS를 하면서 이 문제에서는 해당 노드의 이전 노드가 어디서 왔는지 저장하는 배열 origin을 하나 더 만들어준다.
while(!q.isEmpty()){
int x= q.remove();
if (x>=1){
if (!check[x-1]){
q.add(x-1);
check[x-1]=true;
time[x-1]=time[x]+1;
}
}
if (x+1<=MAX){
if (!check[x+1]){
q.add(x+1);
check[x+1]=true;
time[x+1]=time[x]+1;
}
}
if (2*x<=MAX){
if (!check[2*x]){
q.add(2*x);
check[2*x]=true;
time[2*x]=time[x]+1;
}
}
}원래 origin 없이는 위와 같았던 코드를 아래와 같이 한 줄씩 추가해준다.
while(!q.isEmpty()){
int x= q.remove();
if (x>=1){
if (!check[x-1]){
q.add(x-1);
check[x-1]=true;
time[x-1]=time[x]+1;
origin[x-1]=x;
}
}
if (x+1<=MAX){
if (!check[x+1]){
q.add(x+1);
check[x+1]=true;
time[x+1]=time[x]+1;
origin[x+1]=x;
}
}
if (2*x<=MAX){
if (!check[2*x]){
q.add(2*x);
check[2*x]=true;
time[2*x]=time[x]+1;
origin[2*x]=x;
}
}
}위와 같이 다음 노드로 넘어가면서 이전 노드를 표시해주는 배열을 추가하였다.
이렇게 하면 origin의 배열에 모두 다 전의 노드가 저장이 되어 있다. 이것을 그러면 출력할 수 있는 방법은 무엇일까?
우리가 전의 노드를 저장했기 때문에 역순으로 접근해야 한다는 것을 알 수 있다.
즉 end 부터 시작해서 다음 노드를 origin[해당노드]라는 식으로 전의 노드를 불러낼 수 있다는 것을 알 수 있다.
하지만 우리는 출력은 첫 번째 부터 해야 한다.
이럴 경우에 정말 좋은 자료구조는 스택(Stack)을 활용하는 것이다.
Stack 은 Last In, First Out의 구조를 가지고 있는 자료구조로 나중에 들어간 것이 먼저 나오게 되는 구조이다.
즉 맨 끝부터 시작하여서 처음까지 모두다 스택에 push해주고 pop을 해주게 되면 우리는 첫 노드부터 출력을 할 수 있게 된다.
해당 코드를
Stack<Integer> track=new Stack<>();
for(int i=end; i!=start; i=origin[i]){
track.push(i);
}
track.push(start);
while(!track.isEmpty()){
System.out.print(track.pop()+" ");
}적어보면 위와 같다. stack 에 들어갈 i 는 end 부터 시작하여서 start가 아닐때까지, 다음 i 는 전의 노드를 부르는 식으로 for문을 돌린것이다. 여기서 start가 아닐때까지 stack에 넣어주었으므로 마지막에 start 를 한 번 push해주는 과정이 필요하다.
이후 스택이 비었을 때까지 pop해주면서 결과를 출력하면 된다.
4. 전체 코드
이 모든 과정을 종합한 코드는 아래와 같다.
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int start=sc.nextInt();
int MAX=1000000;
int end=sc.nextInt();
Queue <Integer> q= new LinkedList<>();
boolean check[]=new boolean[MAX+1];
int time[]=new int[MAX+1];
int origin[]=new int[MAX+1];
check[start]=true;
time[start]=0;
q.add(start);
while(!q.isEmpty()){
int x= q.remove();
if (x>=1){
if (!check[x-1]){
q.add(x-1);
check[x-1]=true;
time[x-1]=time[x]+1;
origin[x-1]=x;
}
}
if (x+1<=MAX){
if (!check[x+1]){
q.add(x+1);
check[x+1]=true;
time[x+1]=time[x]+1;
origin[x+1]=x;
}
}
if (2*x<=MAX){
if (!check[2*x]){
q.add(2*x);
check[2*x]=true;
time[2*x]=time[x]+1;
origin[2*x]=x;
}
}
}
System.out.println(time[end]);
Stack<Integer> track=new Stack<>();
for(int i=end; i!=start; i=origin[i]){
track.push(i);
}
track.push(start);
while(!track.isEmpty()){
System.out.print(track.pop()+" ");
}
System.out.println();
}
}