BOJ1697 숨바꼭질

<Solution>

1. BFS 같긴 한데.... 어떤식으로 BFS로 적용 가능할까??

2. BFS라기 보다는 큐 구조체를 사용해서 푸는 문제로 접근(처음에는 순열조합 생각 했는데 시간 터질거 같음)

3. 큐의 front에 넣는 애로 세가지 연산을 다 해가면서 K랑 같은 애를 찾을 때 까지 반복

 

<Source Code>

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

public class BOJ1697_숨바꼭질 {
	
	static int N, K, front = -1, back = -1;
	static int Q[] = new int[100002];
	static int visit[] = new int[100002];
	static int d[] = new int[100002];

	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)
			System.out.print(0);
		else {
			bfs();
			System.out.print(d[back]);
		}
	}
	public static void bfs() {
		Q[++back] = N;
		while(front != back) {
			front++;
			if(Q[front] * 2 < 100001 && Q[front] * 2 >= 0) {
				if(visit[Q[front] * 2] == 0) {
					Q[++back] = Q[front] * 2;
					d[back] = d[front] + 1;
					visit[Q[back]] = 1;
				}
			}
			if(Q[back] == K) break;
			
			if(Q[front] - 1 < 100001 && Q[front] - 1 >= 0) {
				if(visit[Q[front] - 1] == 0) {
					Q[++back] = Q[front] - 1;
					d[back] = d[front] + 1;
					visit[Q[back]] = 1;
				}
			}
			if(Q[back] == K) break;
			
			
			if(Q[front] + 1 < 100001 && Q[front] + 1 >= 0) {
				if(visit[Q[front] + 1] == 0) {
					Q[++back] = Q[front] + 1;
					d[back] = d[front] + 1;
					visit[Q[back]] = 1;
				}
			}
			if(Q[back] == K) break;
		}
	}
}

배열 크기는 100001로 잡으면 터지는데 왜 그런지 도저히 모르겠음.... 그냥 100001 잡았다가 터지길래 하나 더 크게 잡았더니 잘됨 흠...