[C/C++] 백준 17071번 - 숨바꼭질 5 (BFS)

 

<코드>

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

int N, K;
int visit[500001][2];
queue<pair<int, int>> q; // <위치, 시간>

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;

	visit[N][0] = true;
	q.push({ N,0 });

	while (!q.empty())
	{
		int now = q.front().first;
		int time = q.front().second;
		int pos = K + time * (time + 1) / 2;
		q.pop();

		if (pos > 500000)
		{
			cout << -1 << '\n';
			break;
		}

		if (now == pos || visit[pos][time%2])
		{
			cout << time << '\n';
			break;
		}
	
		for (int next : {now - 1, now + 1, 2 * now})
		{
			if (next >= 0 && next <= 500000 && !visit[next][(time+1)%2])
			{
				q.push({ next,time + 1 });
				visit[next][(time+1)%2] = true;
			}
		}

	}
}

 

풀이 방법

 

visit배열을 2차원 배열로 설정한 이유는 홀수초에 방문했는지 짝수초에 방문했는지 check 하기 위한 배열로

visit[17][1]은 홀수초에 17을 방문했다는 의미이다.

 

예를 들어 만약 수빈이가 10초(짝수초)에 위치 X를 방문했다고 가정하고 16초에 동생이 위치 X에 방문한다고 하면  수빈이는 X에서 X-1 또는 X+1로 왔다 갔다 하면서 16초에 동생을 찾을 수 있게 된다.

 

 

www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5