[BOJ]17071:숨바꼭질5

이전의 숨바꼭질 시리즈와는 다르게 시간에 따라 동생의 위치가 바뀐다.

== 이전에 방문했던 좌표를 재방문할 수 있다. (최소시간을 위해)

== BFS로만 돌리면 메모리 초과를 맛볼 수 있다.

 

역시 골드1의 문제... 약간의 아이디어가 필요했다. 헤이 구글

1. 재방문의 경우, 최소 2초가 걸린다. 

2. 수빈이가 각 좌표에 도달하는 최초 시간을 구한다. 

즉, 각 좌표에 도달하는 최소 시간을 구한다면, 해당 좌표는 언제나 2n초 안에 돌아올 수 있다.

2n초 안에 재방문 가능하다는 것은, 최초 시간이 홀수라면 언제나 홀수 시간에, 최초 시간이 짝수라면 언제나 짝수 시간에 방문 가능하다는 것이다. 따라서 짝수로 최초 도달하는 시간, 홀수로 최초 도달하는 시간을 구분해야한다.

int[][] vis = new int[500001][2];

 

해당 아이디어를 이용한다면 나머지 구현은 다른 숨바꼭질 시리즈와 다를게 없다. 

처음에 배열에 좌표별로 동생이 도달하는 시간을 기록하고, 수빈이의 좌표를 BFS로 돌리며 동생을 찾을 수 있는 가장 빠른 시간을 탐색한다. 이때, 수빈이는 동생이 도달하는 시간과 같거나 더 빠르게 도달해야하며, 동생이 홀수초에 도달하였다면 수빈이도 홀수초에, 동생이 짝수초에 도달하였다면 수빈이도 짝수초에 도달해야함을 유의해야한다.

// 동생의 좌표별 도달 시간
int[] target = new int[500001];
int time = 0;
while (K < 500001) {
	target[K] = time;
	time++;
	K += time;
}


int find = Integer.MAX_VALUE; // 동생 최소 발견 시각

// BFS
while (!queue.isEmpty()) {
	int x = cur.x; // 좌표 위치
    	int time = cur.t; // 좌표 방문 시각
	if (target[x] != -1 && vis[x][time % 2] <= target[x] && target[x] % 2 == time % 2) {
		find = Math.min(target[x], find);
	}
    
    // ...
 }

 

https://github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/BFS.DFS/p17071.java

GitHub - SuyeonChoi/Algorithms: Personal Algorithm Study::solving BOJ, Programmers, and SW Expert Academy