백준 17071 숨바꼭질 5 (c++) : 피너클

17071번: 숨바꼭질 5

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

bfs를 이용했다.

 

int n, k;
queue<pair<int, int>> q;
int visited[500001][2];

사용할 변수들이다.

visited는 해당 위치에 언제 도착했는지이다.

visited[50][0] = 50이면 좌표 50에 시간 50만에 도착했다는 뜻이다.

visited[50][1] = 29이면 좌표 50에 시간 29만에 도착했다는 뜻이다.

0에는 해당 좌표에 도착한 짝수 시간이 들어가고

1에는 해당 좌표에 도착한 홀수 시간이 들어간다.

	cin >> n >> k;
	for (int i = 0; i <= 500000; i++) visited[i][0] = visited[i][1] = -1;

	visited[n][0] = 0;

	q.push({ n, 0 });

값들을 입력받고 visited를 -1로 초기화한다.

그 후 visited[n]을 초기화한다. 이때 당연히 0만 초기화해준다. 0초에 도착했으니 말이다.

	while (!q.empty()) {
		int x, t;
		tie(x, t) = q.front();
		q.pop();

		t++;

		if (x - 1 >= 0) if (visited[x - 1][t % 2] == -1) {
			visited[x - 1][t % 2] = t;
			q.push({ x - 1, t });
		}
		if (x + 1 <= 500000) if (visited[x + 1][t % 2] == -1) {
			visited[x + 1][t % 2] = t;
			q.push({ x + 1, t });
		}
		if (x * 2 <= 500000) if (visited[x * 2][t % 2] == -1) {
			visited[x * 2][t % 2] = t;
			q.push({ x * 2, t });
		}
	}

그 다음에는 bfs를 돌려주면 된다.

이렇게 하면 모든 좌표에 도달할수있는 가장 작은 시간이 visited에 들어가게된다.

	int ans = 987654321;

ans를 준비해주고

	for (int i = 0; i <= 1000; i++) {
		
		k += i;

		if (k > 500000) break;
		
		if (i % 2 == 0) {
			if (visited[k][0] == -1) continue;
			if (visited[k][0] > i) continue;

			ans = min(ans, visited[k][0] + (i - visited[k][0]));
		}
		else {
			if (visited[k][1] == -1) continue;
			if (visited[k][1] > i) continue;

			ans = min(ans, visited[k][1] + (i - visited[k][1]));
		}
	}

하나하나 모두 확인해주면 된다.

	for (int i = 0; i <= 1000; i++) {
		
		k += i;

k는 동생의 좌표이다. 매시간마다 계속 더해진다.

		if (k > 500000) break;

50만보다 커지면 바로 종료시킨다.

		if (i % 2 == 0) {
			if (visited[k][0] == -1) continue;
			if (visited[k][0] > i) continue;

			ans = min(ans, visited[k][0] + (i - visited[k][0]));
		}

i는 현재 시간이다. 현재 시간이 짝수라면 visited[0]만 확인하면 된다. 

앞으로 갔다가 다시 뒤로 가면 현재 자리에 돌아오게 된다. 이때 걸리는 시간은 무조건 2이다.

 

만약 visited[k][0]이 -1이라면 현재 좌표에 도달하지 못했다는 의미이다. continue해준다.

만약 visited[k][0]이 i보다 크다면 수빈이는 동생보다 나중에 이 좌표에 도달하게 되는 것이다. continue해준다.

 

이제 수빈이는 동생보다 먼저 이 좌표에 도달했다. 이 좌표에서 왔다갔다 하면서 동생을 기다릴 것이다.

그것이 visited[k][0] + (i - visited[k][0]) 이거다. 현재 좌표에 도달하는 시간 + (동생 도달 시간 - 수빈 도달 시간)

		else {
			if (visited[k][1] == -1) continue;
			if (visited[k][1] > i) continue;

			ans = min(ans, visited[k][1] + (i - visited[k][1]));
		}
	}

홀수일때도 똑같이 해주면 된다.

	if (ans == 987654321) cout << -1 << '\n';
	else cout << ans << '\n';

ans가 987654321이면 한번도 만나지 못했다는 의미이다. -1을 출력한다. 아니면 ans를 출력한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int n, k;
queue<pair<int, int>> q;
int visited[500001][2];

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n >> k;
	for (int i = 0; i <= 500000; i++) visited[i][0] = visited[i][1] = -1;

	visited[n][0] = 0;

	q.push({ n, 0 });

	while (!q.empty()) {
		int x, t;
		tie(x, t) = q.front();
		q.pop();

		t++;

		if (x - 1 >= 0) if (visited[x - 1][t % 2] == -1) {
			visited[x - 1][t % 2] = t;
			q.push({ x - 1, t });
		}
		if (x + 1 <= 500000) if (visited[x + 1][t % 2] == -1) {
			visited[x + 1][t % 2] = t;
			q.push({ x + 1, t });
		}
		if (x * 2 <= 500000) if (visited[x * 2][t % 2] == -1) {
			visited[x * 2][t % 2] = t;
			q.push({ x * 2, t });
		}
	}

	int ans = 987654321;

	for (int i = 0; i <= 1000; i++) {
		
		k += i;

		if (k > 500000) break;
		
		if (i % 2 == 0) {
			if (visited[k][0] == -1) continue;
			if (visited[k][0] > i) continue;

			ans = min(ans, visited[k][0] + (i - visited[k][0]));
		}
		else {
			if (visited[k][1] == -1) continue;
			if (visited[k][1] > i) continue;

			ans = min(ans, visited[k][1] + (i - visited[k][1]));
		}
	}

	if (ans == 987654321) cout << -1 << '\n';
	else cout << ans << '\n';

	return 0;
}

전체코드다.