[BOJ 17071] 숨바꼭질 5 (Java)

BOJ 17071 숨바꼭질 5

문제풀이

문제만 보면 BFS의 느낌이 딱! 오는 그런 문제다. 그러나 시간제한이 0.25초로 굉장히 짧아서 BFS가 아닌가? 하는 의문이 들었다. 그래서...

50만짜리 배열을 만들고 동생이 50만 이하로 도달하는 시간을 모두 기록했다. 그 후 수빈이가 그 시간안에 그 지점에 도달할 수 있는지 확인했다. 사실 이것도 결국 완전탐색으로 확인하는 방식이기 때문에 전혀 도움이 안되는 접근이였다.

그렇다면 BFS로 구현하되 방문체크를 통해서 시간을 줄여야했다. 하지만 단순한 방문체크를 했을 때 돌아오는 연산을 제대로 처리해주지 못한다. 결국 많은 시간을 고민하다가 다른 사람들의 풀이를 통해 깨달았다.

• 수빈이는 -1 연산이 있기 때문에 돌아올 수 있는데 이것을 이용하면 짝수 시간에 방문했던 지점은 짝수 시간에 다시 돌아올 수 있고 홀수 시간에 방문한 지점은 홀수 시간에 다시 돌아올 수 있다. 따라서 홀짝에 따라서 방문체크를 나눈다면 방문체크가 가능하다.
• 따라서 수빈이와 동생이 딱 만났을 때의 시간 뿐만 아니라 수빈이가 홀수 또는 짝수 시간에 먼저 방문한 지점에 같은 홀수 또는 짝수 시간에 동생이 방문한다면 수빈이가 돌아올 수 있기 때문에 만난것과 같다.

구현코드

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 final int MAX = 500000;
	static final int ODD = 1;
	static final int EVEN = 0;
	
	static Queue<Integer> q;
	static boolean[][] visited;
	static int subin, brother;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		q = new LinkedList<>();
		visited = new boolean[2][MAX + 1];
		
		subin = Integer.parseInt(st.nextToken());
		brother = Integer.parseInt(st.nextToken());
		
		if(subin == brother) {
			System.out.println(0);
			return;
		}
		
		q.offer(subin);
		
		System.out.println(bfs());
	}

	private static int bfs() {
		int layer = 0;
		int time = 0;
		int young = brother;
		
		while(!q.isEmpty()) {
			int size = q.size();
			
			layer = time % 2 == 0 ? EVEN : ODD;
			
			for(int i = 0 ; i < size ; ++i) {
				int old = q.poll();
				
				if(old == young) return time;
				
				if(old * 2 <= MAX) {
					if(!visited[layer][old * 2]) {
						visited[layer][old * 2] = true;
						q.offer(old * 2);
					}
				}
				if(old + 1 <= MAX) {
					if(!visited[layer][old + 1]) {
						visited[layer][old + 1] = true;
						q.offer(old + 1);
					}
				}
				if(old - 1 >= 0) {
					if(!visited[layer][old - 1]) {
						visited[layer][old - 1] = true;
						q.offer(old - 1);
					}
				}
			}
			
			young += ++time;
			if(young > MAX) return -1;
			if(visited[layer][young]) return time;
		}

		return -1;
	}
}