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

https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

동생이 이동하는 것을 확인하면서 동생이 어떤 시간에 어디에 위치하는지 "discovered1[위치] = 도착 시간"에 표시하고, 수빈이 이동하는 것을 확인하면서 수빈이 어떠한 위치에 짝수(홀수) 시간에 도착하면, 해당 도착시간 이상의 짝수(홀수) 시간에 모두 도달할 수 있음을 이용해서 "discovered2[위치][짝수:0, 홀수:1] = 도착시간"을 표시하고, 이를 이용해 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int n, k;

//동생이 어느 시간에 어디에 위치하는지 체크
vector<int> discovered1(500005, -1); //[위치] = 도착 시간
queue<int> q1; //(위치)

//수빈이 어떠한 위치에 짝수(홀수)시간에 도착하면, 해당 도착시간 이상의 짝수(홀수)시간에 모두 도달할 수 있음을 이용
vector<vector<int>> discovered2(500005, vector<int>(2, -1)); //[위치][짝수:0, 홀수:1] = 도착시간
queue<pair<int, int>> q2; //(위치,시간)

int solve(int start1, int start2) {

	discovered1[start1] = 0;
	q1.push(start1);

	while (!q1.empty()) {
		int here = q1.front();
		q1.pop();

		int there_depth = discovered1[here] + 1;
		int there = here + there_depth;
		if (there <= 500000) {
			discovered1[there] = there_depth;
			q1.push(there);
		}
	}

	discovered2[start2][0] = 0;
	q2.push(make_pair(start2, 0));

	int result = 987654321;

	while (!q2.empty()) {
		int here = q2.front().first;
		int depth = q2.front().second;
		q2.pop();

		//here에서 동생을 만날 수 있을때
		//동생이 here을 지나는 시간이 짝수 또는 홀수로 수빈과 같고, 동생이 지나는 시간이 수빈이 지나는 시간 이상일때
		if (discovered1[here] != -1 && ((discovered1[here] % 2) == (depth % 2)) && discovered1[here] >= depth) {
			result = min(result, discovered1[here]);
			continue;
		}

		int there;
		int there_depth = depth + 1;

		//걸을때
		there = here + 1;
		if (there >= 0 && there <= 500000 && discovered2[there][there_depth % 2] == -1) {
			discovered2[there][there_depth % 2] = there_depth;
			q2.push(make_pair(there, there_depth));
		}

		there = here - 1;
		if (there >= 0 && there <= 500000 && discovered2[there][there_depth % 2] == -1) {
			discovered2[there][there_depth % 2] = there_depth;
			q2.push(make_pair(there, there_depth));
		}

		//순간이동 할때
		there = here * 2;
		if (there >= 0 && there <= 500000 && discovered2[there][there_depth % 2] == -1) {
			discovered2[there][there_depth % 2] = there_depth;
			q2.push(make_pair(there, there_depth));
		}
	}

	if (result == 987654321) {
		return -1;
	}

	return result;
}


int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	cout << solve(k, n);

	return 0;
}