백준 17071번 숨바꼭질 5

문제 링크입니다: https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

동생의 위치가 계속 움직이기 때문에 기존 숨바꼭질 문제들의 심화 버전이었습니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 N이 너무 크기 때문에 `visited[수빈이의 위치][경과한 초]`와 같이 이차원 배열을 선언하지 못합니다.

1.1 이 문제의 핵심은 수빈이가 [+1, -1] 혹은 [-1, +1]과 같이 이초에 걸쳐 동일한 위치로 이동할 수 있다는 점이었습니다.

1.2 이로 인해, 홀수 초 또는 짝수 초에 동생이 특정 위치에 도달했을 때, 수빈이가 해당 위치에 이미 홀수 초 또는 짝수 초에 방문했다면 결국 두 사람이 만날 수 있다는 것을 의미합니다.

• 두 번째 예제를 들자면 수빈이는 17에서 출발해 [-1, -1] 움직이면 15에 2초 만에 도착
• 동생은 5에서 시작해 4초가 경과하면 15에 도착
• 수빈이가 2초 만에 도착한 15 지점에서 [-1, +1] 혹은 [+1, -1] 움직이면 4초에 동생과 15에서 만남
• 따라서 `visited[수빈이의 위치][경과한 초]`가 아닌 `visited[수빈이의 위치][경과한 초 % 2]`로 선언해 공간복잡도를 줄일 수 있음

 

2. 1번의 로직대로 BFS 알고리즘을 구현하면 AC 받을 수 있는 문제였습니다.

 

* 주의: N과 K가 동일할 때 예외처리를 해줘야 합니다.

 

	#include <iostream>
	#include <queue>
	#include <algorithm>
	using namespace std;
	const int MAX = 5e5 + 1;
	typedef struct
	{
	int location, second;
	} State;
	int N, K;
	int getSum(int num)
	{
	return num * (num + 1) / 2;
	}
	bool visited[MAX][2];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	if (N == K)
	{
	cout << 0 << "\n";
	return 0;
	}
	queue<State> q;
	q.push({ N, 0 });
	visited[N][0] = 0;
	while (!q.empty())
	{
	int curLocation = q.front().location;
	int curSecond = q.front().second;
	q.pop();
	int target = K + getSum(curSecond);
	if (target >= MAX)
	{
	break;
	}
	if (visited[target][curSecond % 2])
	{
	cout << curSecond << "\n";
	return 0;
	}
	if (curLocation + 1 < MAX && !visited[curLocation + 1][(curSecond + 1) % 2])
	{
	visited[curLocation + 1][(curSecond + 1) % 2] = true;
	q.push({ curLocation + 1, curSecond + 1 });
	}
	if (curLocation - 1 >= 0 && !visited[curLocation - 1][(curSecond + 1) % 2])
	{
	visited[curLocation - 1][(curSecond + 1) % 2] = true;
	q.push({ curLocation - 1, curSecond + 1 });
	}
	if (curLocation * 2 < MAX && !visited[curLocation * 2][(curSecond + 1) % 2])
	{
	visited[curLocation * 2][(curSecond + 1) % 2] = true;
	q.push({ curLocation * 2, curSecond + 1 });
	}
	}
	cout << -1 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~