[Java Algorithm] 숨바꼭질 4 BOJ #13913

문제

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

13913번: 숨바꼭질 4

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static Deque<int[]> que;
	static boolean[] visited = new boolean[100_001];
	static int[] parent = new int[100_001];
	static int n, k;
	
	public static int[] bfs() {
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int sec = now[1];
			int[] cal = {x+1, x-1, x*2};
			
			for(int i = 0; i < 3; i++) {
				if(cal[i] == k) {
					visited[cal[i]] = true;
					parent[cal[i]] = x;
					return new int[]{cal[i], sec+1};
				}
				if(cal[i] < 0 || cal[i] >= visited.length || visited[cal[i]]) continue;
				
				que.add(new int[]{cal[i], sec+1});
				visited[cal[i]] = true; 
				parent[cal[i]] = x; // 이전에 어디서 이어진건지 기록해두기
			}
		}
		return new int[]{};
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		if(n == k) {
			System.out.println(0 + "\n" + n);
		}
		else {
			visited[n] = true;
			parent[n] = n;
			que = new ArrayDeque<>();
			que.add(new int[]{n, 0});
			
			// 거꾸로 탐색하면서 이어진 노드들 stack에 넣었다가 다시 빼면서 출력
			Stack<Integer> stack = new Stack<>();
			int[] result = bfs();
			int idx = result[0];
			while(idx != n) {
				stack.push(parent[idx]);
				idx = parent[idx];
			}
			
			out.append(result[1] + "\n");
			while(!stack.isEmpty()) {
				out.append(stack.pop() + " ");
			}
			System.out.println(out.append(result[0]));
		}
	}

}

👉 BFS 문제
이 문제는 발생 가능한 시간 초과, 메모리 초과, 예외들을 잘 생각해주어야 하는 것 같음

• 시작점과 도착점이 같을 경우 따로 빼서 처리해주었다.
• visited는 단순히 방문 처리를 하는 배열이며,
  parent는 현재 인덱스에 오기 전에 방문한 인덱스를 저장하는 배열이다.
  (원래는 이 두 배열을 하나로 묶고, int형으로 만들어 사용했지만
  그렇게 하면 시작점이 0일 경우 예외가 발생하여 메모리 초과가 발생한다.)
• bfs 메서드는 int[]형을 반환하도록 하여서 {도착 인덱스, 걸린 시간}을 함께 가져왔다.
• bfs 메서드의 경우 아주 간단한데, 하나 체크할 점은
  parent에 이전에 들린 인덱스 정보를 꼭 넣어줄 것,,!!
• bfs 메서드가 반환되면 스택에 도착지점부터 거꾸로 경로를 넣어준 후,
  다시 pop하면서 처음 시작 지점부터 차례대로 출력할 수 있게 했다.

 

💡 피드백

• 숨바꼭질3 문제와 매우 유사하지만, 여러 가지 예외를 잘 체크해줘야 하는 문제였다.
• 처음엔 쉽네~~ 했다가,, 정답률 낮은 이유를 알아버렸다.ㅎㅎ