[C언어 / 백준 - 17071] DFS/BFS

www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

2

 

 

숨박꼭질 문제 중 가장 상위 난이도에 속하는 문제로 다른 문제와 달리 동생의 위치가 계속해서 변하는 것이 특징이다.다른 문제들은 BFS를 이용하여 해당 위치에만 도달하면 시간을 출력하는 문제였지만 이 문제는 언니의 위치와 동생의 위치를 함께 고려해야하기에 다른 문제보다 난이도가 높다.

 

나도 이 문제를 풀 때 전에 풀었던 문제들과 동일하게 풀려했고 그 알고리즘은 시간초과가 나 풀 수 없었다. 그럴만한게 이 문제의 시간 제한은 0.25초로 최악의 경우 500,000이 오면 절대 해결 할 수 없다.

 

-> 예제를 예로 설명을 해보자면 언니의 위치는 5,동생의 위치는 17로 둘다 위치가 변하지만 언니의 위치는 -1과 +1을 동시에 하기에 2번의 반복을 하게 되면 다시 원래 위치로 돌아오게 된다. 똑같이 모든 위치가 그렇게 되기에 이걸 이용하는 것이다.

 

언니의 이동 범위 폭이 훨씬 넓기 때문에 동생의 위치에 미리 가있어 동생을 기다리는 것으로 생각하면 된다. 여기서 고려해야할 것이 하나 존재하는데, 언니가 짝수 시간대에 해당 위치에 도달하면 +2초 후에 다시 해당 위치로 되돌아오고 그 시간대에 또 +2초 후에 도달한다.

 

즉, 짝수 시간대에 어떤 한 위치에 도달하게 되면 똑같이 짝수 시간대에 해당 위치에 반복해서 돌아온다는 것이다. 홀수도 마찬가지이다. 그렇기 때문에 언니가 짝수 시간대에 한 지점에 도달했고 동생이 홀수 시간대에 같은 지점에 도달했다고 하더라도 시간 대가 다르기에 만날 수가 없다는 것이다. 

 

이것들을 고려하여 코드를 작성하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define MAX_SIZE 500003
#define MAX_Q 1000003
struct node {
	int x;
};

int head = 0, tail = 0, size =0;
struct node queue[MAX_Q]; 

int visited[2][MAX_SIZE];
int N, K;
bool ok;

const int max_n = 500000;
int dx[3] = { -1,1,0 };
int dm[3] = { 1,1, 2 };

void enque(int x_) {
	struct node temp;
	temp.x = x_;
	queue[tail] = temp;
	tail = (tail + 1) % MAX_Q;
	size++;
}

struct node deque() {
	struct node temp = queue[head];
	head = (head + 1) % MAX_Q;
	size--;
	return temp;
}

int Is_Empty() {
	if (head == tail) {
		return 0;
	}
	else {
		return 1;
	}
}

int BFS() {
	int time = 1;
	while (Is_Empty()) {
		K += time;
		if (K > max_n) break;

		if (visited[time % 2][K]){
			ok = true;
			break;
		}
		int thisTrunSize = size;
		for (int i = 0; i < thisTrunSize; i++) {
			struct node k = deque();
			for (int j = 0; j < 3; j++) {
				int nx = (k.x + dx[j]) * dm[j];
				if (nx<0 || nx>max_n) continue;
				if (nx == K) {  ok = true; break; }
				if (visited[time % 2][nx]) continue;
				visited[time % 2][nx] = 1;
				enque(nx);
			}
			if (ok) break;
		}
		if (ok) break;
		time++;
	}
	if (ok) return time;
	else return -1;
}

int main() {
	scanf("%d %d", &N, &K);
	enque(N);
	visited[0][N] = 1;

	if (N == K) {
		printf("0\n");
		return 0;
	}
	printf("%d\n",BFS());
	
	return 0;
}