[BOJ | 백준] 17071번: 숨바꼭질 5

by Kimcoding on 2020-02-12 01:14

in BOJ

문제 설명

BOJ 17071

수빈이와 동생이 숨바꼭질을 하는데 서로 위치가 주어지고 수빈이는 초마다 +1, -1, *2로 이동할 수 있고

동생은 앞으로만 가는데 가속이 붙습니다. 수빈이가 동생을 찾는 최소 시간을 구하면 됩니다.

풀이

문제를 읽어보면 bfs문제입니다.

하지만 수빈이의 모든 이동을 하며 동생을 찾게 되면 시간이 초과됩니다.

그래서 수빈이가 중복된 곳은 가지 않도록 해주셔야 합니다.

그럼 visit[위치][시간]에다가 방문을 체크하면 될까요..?

위치가 최대 50만이고 시간이 1000정도 까지 나올 수 있습니다.

그래서 메모리와 시간을 더 줄여야하는데 어떻게 할까요…

수빈이는 +1,-1 이동을 할 수 있습니다.

이 말은 현재 위치에서 2번의 이동 후에 현재 위치로 되돌아 올 수 있다는 걸 뜻합니다.

그렇다면 수빈이가 5위치에 1초 만에 도착을 했다면 1,3,5,7,9··· 초에는 다 그 위치에 있을 수 있습니다.

초가 홀수, 짝수인지만 구분을 하면 됩니다.

그래서 수빈이가 방문을 할때 마다 visit[위치][홀수 | 짝수]에 저장을 해주면 됩니다.

그렇게 되면 탐색 횟수를 줄이고 답을 구할 수 있습니다.

k도 초가 증가할때 마다 위치를 변경하여 방문을 확인하고 체크가 되어있으면 답을 출력

끝까지 못 찾거나 50만 밖으로 나가면 -1을 출력하면 됩니다.

소스 코드

#include <cstdio>
#include <queue>
#define MAX 500000
using namespace std;
typedef pair<int, int> pii;

int n, k, cnt;
bool visit[MAX + 1][2];
queue <pii> q;

int solve() {
	q.push({ n,0 });
	visit[n][0] = 1;
	while (q.size()) {
		if (visit[k][cnt & 1]) return cnt;
		int now = q.front().first, num = q.front().second; q.pop();
		if (num > cnt) k += (++cnt);
		if (k > MAX) break;
		int dir[3] = { -1,1,now };
		for (auto d : dir) {
			if (now + d < 0 || now + d > MAX) continue;
			if (visit[now + d][(num + 1) & 1]) continue;
			q.push({ now + d,num + 1 });
			visit[now + d][(num + 1) & 1] = 1;
		}
	}
	return -1;
}

int main() {
	scanf("%d %d", &n, &k);
	printf("%d\n", solve());
	return 0;
}