[백준 JAVA] 13913번: 숨바꼭질 4

https://www.acmicpc.net/problem/13913

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static int N, K, ans = 0;
	public static int[] time, before;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		// 1. 입력받기
		N = sc.nextInt();
		K = sc.nextInt();
		time = new int[100001];
		before = new int[100001];
		
		// 2. 예외 처리
		if(N == K) { // 수빈이랑 동생이 같은 위치에 있는 경우
			sb.append(ans + "\n");
			sb.append(N);
			System.out.println(sb);
			return;
		} else if(N > K) { // 수빈이가 동생보다 더 큰 위치에 있는 경우
			ans = N - K;
			sb.append(ans + "\n");
			for(int i=N;i>=K;i--) {
				sb.append(i + " ");
			}
			System.out.println(sb);
			return;
		}
		// 동생이 수빈이보다 더 큰 위치에 있는 경우
		// 3. BFS
		Queue<Integer> q = new LinkedList<>();
		q.offer(N);
		time[N] = 1;
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			if(cur == K) {
				ans = time[cur] - 1;
				break;
			}
			
			
			int next;
			
			for(int i =0;i<3;i++) {
				
				if(i == 0) {
					next = cur + 1;
				} else if (i == 1) {
					next = cur - 1;
				} else {
					next = cur * 2;
				}
				
				if(next < 0 || next > 100000) {
					continue;
				}
				
				if(time[next] == 0) {
					time[next] = time[cur] + 1;
					before[next] = cur;
					q.offer(next);
				}
				
			}
			
		}
		
		sb.append(ans + "\n");
		
		Stack<Integer> st = new Stack<>();
		int cnt = K;
		st.add(K);
		while(cnt != N) {
			cnt = before[cnt];
			st.push(cnt);
		}
		
		while(!st.isEmpty()) {
			sb.append(st.pop() + " ");
		}
		
		
		System.out.println(sb);
	}

}

 

## 풀이 사항
풀이 일자: 2024.09.30
풀이 시간: 2일
채점 결과: 정답
예상 문제 유형: BFS

## 풀이방법
1. 수빈의 위치 N 이 동생의 위치 K 와 같을때, N > K, N <K일때를 각각 나눠서 풀이
2. N > K 일때는 최적해가 계속 N을 1씩 줄여서 K로 가는 방법밬에 없다.
3. N > K 일때 time, before 배열을 만들어 각각 그 위치로 갔을때 걸린 시간과 그 위치로 가기 전의 위치를 저장해준다.
4. q에 먼저 N을 넣어주고 범위를 초과하지 않고, 도착했던 적이 없는 위치 (time[next] == 0)라면 time, before에 값을 저장해주고 그 위치를 큐에 저장해준다.  
5. K에 도착한다면 BFS이므로 가장 먼저 도착했을 때 그 시간이 최적해임이 보장되므로 while문을 빠져나온다.
6. stack을 이용하여 경로를 출력해준다.

## 반성
1. 처음에 방문체크를 before[next]가 0일때를 기준으로 했더니 50퍼에서 메모리 초과가 생겼다.
2. 생각해보니 위치가 그 전의 위치가 0이고 next로 가는 경우 q에서 무한 루프가 생긴다.