[Java Algorithm] 숨바꼭질 2 BOJ #12851

문제

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

12851번: 숨바꼭질 2

 

내 문제 풀이

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

public class BOJ_12851 {
	static Deque<int[]> que;
	static int[] visited = new int[100_001];
	static int n, k, cnt;
	
	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 최솟값 갱신
					if(visited[k] > sec+1) {
						visited[k] = sec+1;
						cnt = 1;
					} else if(visited[k] == sec+1) {
						cnt++;
					}
					continue;
				}
				if(cal[i] < 0 || cal[i] >= visited.length || visited[cal[i]] <= sec) continue;
				
				que.add(new int[]{cal[i], sec+1});
				visited[cal[i]] = sec+1;
			}
		}
		return visited[k];
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());;
		
		if(n == k) System.out.println(0 + "\n" + 1);
		else {
			for(int i = 0; i < visited.length; i++) visited[i] = Integer.MAX_VALUE;
			que = new ArrayDeque<>();
			que.add(new int[]{n, 0});
			
			System.out.println(bfs() + "\n" + cnt);
		}		
	}

}

👉 BFS 문제

✔️ #13549 숨바꼭질3 문제와 매우 유사!

 

• visited 배열을 이용하여 매 자리의 최소 탐색 시간을 업데이트해준다는 점은 숨바꼭질3 문제와 같다.
• 이 문제의 포인트는 동생을 만났을 때!!
  동생을 만났을 때, visited 배열의 동생 자리인 visited[k] 자리에 저장되어있는 값이
  현재 탐색하는 경로의 시간보다 더 크다면, 당연히 visited[k]의 최솟값을 갱신해줘야한다.
  그런데 이 때 visited[k]만 갱신시켜줄 것이 아니라, cnt도 함께 초기화해줘야 한다.
• 동생을 찾는데 걸린 시간의 최솟값이 변경된다는 것은
  그 전까지 누적했던 해당 최소 탐색 시간에 대한 카운팅도 새롭게 해야한다는 의미이기 때문!
• 그리고 만약 visited[k] 값이 현재 탐색하는 경로의 시간과 같다면 그대로 cnt를 증가시켜 카운팅했다.

 

💡 피드백

• 모든 자리마다, 시간은 같아도 경로는 다를 수 있다는 점을 캐치해주면 되는 문제였다.