백준 12851 - 숨바꼭질 2

Java

12851 번 - 숨바꼭질 2

문제

접근 방법

숨바꼭질 1문제에서 가장 빠른 시간으로 찾는 방법의 개수를 구하는 문제가 추가되었다.

따라서, 이전 문제와 같이 방문 여부를 나타내는 100,000개의 배열과 BFS를 이용하여 해겷하는데,
여기서 최종 k번째에 도착하였을 때 종료하지 않고, 최단 시간에 도달한 횟수를 추가로 세어준다.

그리고 주의해야할 점은 각 지점에 방문하였을 때 바로 방문 처리를 하는 것이 아닌, queue에 저장 후 poll 되어 자신의 차례가 되었을 때 방문 처리를 해주어야 한다.

이유는 1 -> 2(+ 1) -> 4와 1 -> 2(* 2) -> 4일 때 2가지 방법이 존재하는데,
만약 1의 시작점에서 (+1)로 2에 도달하자마자 방문처리를 하면 * 2를 통해 2에 도달할 수 없으므로, 한번 나중에 방문처리를 하여 2가지 경우의 수 동시에 2에 도달 할 때 방문처리 하여야 한다.

코드

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

public class Main {
	static int n, k, result = 9999999, count;
	static boolean[] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	
    	vis = new boolean[100001];
    	
    	BFS();
    	if(n == k) {
    		result = 0;
    		count = 1;
    	}
    	System.out.println(result);
    	System.out.println(count);
    	
    	br.close();
	}
	
	static void BFS() {
		
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {n, 0});
		int[] q;
		int curN, time;
		vis[n] = true;
		while(!queue.isEmpty()) {
			q = queue.poll();
			curN = q[0];
			time = q[1];
			
			vis[curN] = true;
			
			if(curN == k) {
				if(time < result) {
					count = 1;
					result = time;
				}
				else if(time == result){
					count++;
				}
			}
			
			if(curN + 1 <= 100000 && !vis[curN + 1]) 
				queue.add(new int[] {curN + 1, time + 1});
				
			if(curN - 1 >= 0 && !vis[curN - 1])
				queue.add(new int[] {curN - 1, time + 1});
			
			if(curN * 2 <= 100000 && !vis[curN * 2])
				queue.add(new int[] {curN * 2, time + 1});
		}
	} 
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점