[BOJ 13913] 숨바꼭질 4 (Java)

BOJ 13913 숨바꼭질 4

문제풀이

각 지점에서 +1, -1, *2의 다음 지점을 선택할 수 있으며, 목표 지점까지의 최단 시간을 구하는 문제기 때문에 BFS를 생각하게 되었다. 하지만, 기존에 BFS를 구현할 때 class를 만들어서 하곤 했는데 이 문제의 경우에는 시간 초과로 인해서 더 가볍고 빠른 BFS를 구현해야했다.

검색하던 도중 좋은 코드를 발견하게 되었고 가져왔다.

• 이 코드에서는 int형 배열 하나를 통해 방문 체크, 경로 역추적을 모두 수행하였다.
• 큐의 사이즈 만큼 반복함으로써 BFS 함수 내에서 depth를 가질 수 있다.
  - 나는 원래 class 안에 depth를 가지고 있게 했었다.
• int[] next = { cur + 1, cur - 1, cur * 2}; 이렇게 배열 선언을 함으로써 마치 방향 탐색에서 진행을 반복문 안에서 수행하던 것과 같이 코드를 많이 줄일 수 있게 되었다.

구현코드

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

public class Main {
	
	static final int MAX = 100000;
	static int N, K, time;
	static int[] ways;
	static Queue<Integer> q;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		if(N != K) { // N과 K가 같은 경우에는 잡은 것이기 때문에 바로 끝낸다. 
			ways = new int[MAX + 1];
			q = new LinkedList<>();
			
			// ways는 이전 방문을 확인하는 visited와 지나온 경로를 역추적하는 역할을 한다. 
			Arrays.fill(ways, -1);
			q.offer(N);
			
			time = bfs();
			sb.append(time + "\n");
			
			int[] result = new int[time + 1];
			int before = K;
			for(int i = time ; i >= 0 ; --i) {
				result[i] = before;
				before = ways[before];
			}
			
			for(int i = 0 ; i <= time ; ++i) {
				sb.append(result[i] + " ");
			}
		} else {
			sb.append(0 + "\n" + N);
		}
		
		System.out.println(sb.toString());
	}

	private static int bfs() {
		int depth = 0;
		
		while(!q.isEmpty()) {
			depth++;
			int size = q.size();
			
			// size를 구하고 기존에 큐에 있던 만큼만 반복함으로써 몇번째 depth인지 알 수 있다. 
			for(int i = 0 ; i < size ; ++i) {
				int cur = q.poll();
				// 다음과 같이 배열을 선언하므로써 코드를 많이 줄일 수 있었다.
				int[] next = { cur + 1, cur - 1, cur * 2};
				
				for(int j = 0 ; j < 3 ; ++j) {
					if(next[j] >= 0 && next[j] <= MAX &&
					   ways[next[j]] == - 1) { // 이전 방문 여부 확인
						ways[next[j]] = cur; // 방문했다고 기록 
						
						if(next[j] == K) return depth; // 다음으로 방문할 곳이 K면 depth를 리턴 
						
						q.offer(next[j]);
					}
				}
			}
		}
		return -1;
	}
}