[Java]백준 BaekJoon.AC 12851 : 숨바꼭질2 (너비우선탐색-bfs, Queue)

 

 

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

12851번: 숨바꼭질 2

 

 

이 문제도 N-Queue 문제처럼 시간을 단축시킬 수 있는 방법을 찾는게 관건인 것 같다.

아래와 같은 방식을 사용하지 않으면 시간초과가 일어나는지는 모르겠지만, 굳이 단축시키지 않을 이유는 없으니..

 

우선, 수빈이가 동생보다 더 오른쪽에 있다면 가능한 방법은 (X-1)뿐이다.

왼쪽으로 한칸씩 총총 이동하는 방법밖에 존재하지 않으니,

(N>=K) 일 때 걸리는 시간은 (N-K), 가짓수는 1이 되시겠다.

 

이 코드만으로도 벌써 전체 경우의 수 중에서 반절이 단순 연산으로 해결된다.

나머지 반절은 제대로 된 코드를 이용해 해결한다.

 

Queue를 사용하고 싶었는데... 쉽진 않았다.

처음엔 time을 하나씩 올려가며 bfs를 일일이 통제하려 했다.

그러려면 time 한세트(같은 가짓수일때)가 끝나는 경우와 시작되는 경우를 체크해줘야 했다.

구현은 시켰는데(불굴의 의지) 음.... 설명하기 애매하지만...

같은 time 내에선 'A->C로 가는 경우'와 'B->C로 가는 경우' 모두 카운트해줘야 하는데, 여기서 문제가 발생했다.

필자는 boolean을 이용한 visit 1차원 배열을 이용해 방문 여부만 체크하다가 난관에 봉착했다.

이미 visit했지만 예외적으로 같은 time내에선 visit을 허용해줘야 했기 때문이다.

 

 

결국 visit배열을 포기하고 int 1차원배열을 사용했다.

이 배열에 각 칸에 맞는 time을 기록하고 조건에 따라 리뉴얼하기로 했다.

time이 각각 기록되어 있으니, 같은 time 내 방문한 칸인지 확인하기 편했다.

 

중간중간 조건을 빠트려서 채워넣느라 쉽진 않았다...

bfs는 친숙하면서 늘 익숙하지 않다..

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, K;
	static int[] arr = new int[100001];
	static int time = 999999;
	static int many = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		if(N>=K) {
			time = N - K;
			many = 1;
		}else {
			cal();
		}
		
		System.out.println(time);
		System.out.println(many);
		
	}
	
	public static void cal() {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(N);
		arr[N] = 1;
		
		while(!queue.isEmpty()) {
			
			int temp = queue.poll();
			int X;
			
			if(time < arr[temp]) {
				return;
			}
			
			for(int i=0; i<3; i++) {
				
				if(i==0)       X = temp - 1;
				else if(i==1)  X = temp + 1;
				else           X = 2 * temp;
				
				if(X<0 || X>100000) continue;
				
				if(X==K) {
					many++;
					time = arr[temp];
				}
				
				if(arr[X]==0 || arr[X]==arr[temp]+1) {
					arr[X] = arr[temp] + 1;
					queue.add(X);
				}
			}
			
		}
		
	}
}