[백준: Java] 13913 - 숨바꼭질 4

[문제]

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

일반적인 그래프 형태의 BFS가 아닌 특이한 형태의 BFS입니다. 

 

해당 시리즈 문제를 풀어본 경험이 있어서 풀 수 있었고, 처음 해당 유형의 문제를 풀 때는 정답을 보고 이해했었습니다.

 

해당 문제는 BFS + 경로 역추적을 수행하는 문제로 보면 되겠습니다.

---

[초기화]

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, k;
	static int[] time;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		solve();
	}

time은 일종의 visited 배열로, 도착한 시간을 기록함으로써 해당 위치에 방문을 표시하는 용도입니다.

---

[풀이]

	static void solve() {
		time = new int[100001];
		Queue<Integer> q = new ArrayDeque<>();
		int[] trace = new int[100001];
		q.add(n);
		
		if (n == k) { // 시작점과 목표가 같을 때
            System.out.println(0);
            System.out.println(n);
            return;
        }

		while(!q.isEmpty()) {
			int current = q.poll();
			
			for(int i: new int[] {current - 1, current + 1, current * 2}) {
				if(0 <= i && i <= 100000 && time[i] == 0) {
					time[i] = time[current] + 1;
					q.add(i);
					trace[i] = current;
					
					if(i == k) 
						print_result(trace, i);
				}
			}
		}
	}

문제의 제약사항에 따르면 N과 K는 동일한 제약사항을 가지므로, 둘 이 같을 때를 바로 처리해 줍니다.

 

그 외에는 BFS를 수행합니다.

1. 시작 위치(N) 기록
2. 시작 위치에서 갈 수 있는 위치 탐색
3. 갈 수 있는 위치가 탐색 범위를 벗어나지 않고, 아직 방문하지 않았다면
   1. 현재위치까지 기록된 시간 + 1을 갈 수 있는 위치에 저장
   2. 다음 탐색을 위해 큐에 저장
   3. 이동 경로를 표시하기 위해 역추적 값 저장 → 해당 위치에 도달하기 전에 있던 위치 저장
4. 최종 목적지(K)에 도달했다면
   1. 값 출력

	static void print_result(int[] trace, int current) {
		Stack<Integer> result = new Stack<>();
		result.add(k);
		
		while(true) {
			current = trace[current];
			result.push(current);
			if(current == n)
				break;	
		}
		
		System.out.println(time[k]);
		while(!result.isEmpty())
			System.out.print(result.pop() + " ");
	}

1. 도착 지점 스택에 저장
2. 역추적 배열을 통해 값을 저장해 나가면서 시점 지점까지 이동
3. 도착 지점까지 걸린 시간 출력
4. 스택에 저장한 값을 하나씩 출력

---

[전체 코드]

package 백준.골드;

import java.util.*;
import java.io.*;

public class BOJ_13913_숨바꼭질4 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, k;
	static int[] time;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		solve();
	}
	
	static void print_result(int[] trace, int current) {
		Stack<Integer> result = new Stack<>();
		result.add(k);
		
		while(true) {
			current = trace[current];
			result.push(current);
			if(current == n)
				break;	
		}
		
		System.out.println(time[k]);
		while(!result.isEmpty())
			System.out.print(result.pop() + " ");
	}
	
	static void solve() {
		time = new int[100001];
		Queue<Integer> q = new ArrayDeque<>();
		int[] trace = new int[100001];
		q.add(n);
		
		if (n == k) { // 시작점과 목표가 같을 때
            System.out.println(0);
            System.out.println(n);
            return;
        }

		while(!q.isEmpty()) {
			int current = q.poll();
			
			for(int i: new int[] {current - 1, current + 1, current * 2}) {
				if(0 <= i && i <= 100000 && time[i] == 0) {
					time[i] = time[current] + 1;
					q.add(i);
					trace[i] = current;
					
					if(i == k) 
						print_result(trace, i);
				}
			}
		}
	}
}

처음엔 모든 범위를 다 탐색하니까 시간초과가 발생했습니다.

 

그래서 탐색을 돌다가 목적지를 만나면 바로 결과를 출력하도록 수정했고, 최종적으로 통과되었습니다.

---