[BOJ 14714 // C++] 홍삼 게임 (Easy)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14714번 문제인 홍삼 게임 (Easy)이다.
문제는 아래 링크를 확인하자.

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

14714번: 홍삼 게임 (Easy)

게임 진행 상태를 (지목권A를 가진 사람, 지목권B를 가진 사람, 이번에 지목을 할 사람이 누구인가)로 구성된 3-tuple로 표현할 수 있다. 그리고 각 상태에서 지목을 하는 것으로 다음 상태로 넘어갈 수 있다.

 

위 튜플의 가능한 경우의 수는 500*500*2 미만이므로, (A, B, A차례) 튜플에서 시작해 지목권A를 가진 사람과 지목권B를 가진 사람이 동일인물이 되는 때까지 BFS탐색을 하는 것으로 문제를 해결할 수 있다.

 

입력받은 A와 B에서 1을 빼 0-based 구현을 할 수 있다. 0-based로 구현을 하면 DA와 DB만큼의 이동을 나머지연산으로 간단히 표현하기 좋아진다.

 

아래는 제출한 소스코드이다.

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

int N, A, B, dA, dB;
int dist[500][500][2]; // (A, B, 0:A가움직일차례, 1:B가움직일차례)

int bfs() {
	queue<pair<pair<int, int>, int>> que;
	que.push(make_pair(make_pair(A, B), 0));
	dist[A][B][0] = 1;
	while (!que.empty()) {
		int a = que.front().first.first, b = que.front().first.second, k = que.front().second;
		que.pop();

		if (a == b) return dist[a][b][k] - 1;

		if (k == 0) { // A가 움직일 차례
			int tmp;
			tmp = (a + dA) % N;
			if (dist[tmp][b][k ^ 1] == 0) {
				dist[tmp][b][k ^ 1] = dist[a][b][k] + 1;
				que.push(make_pair(make_pair(tmp, b), k ^ 1));
			}
			tmp = (a - dA + N) % N;
			if (dist[tmp][b][k ^ 1] == 0) {
				dist[tmp][b][k ^ 1] = dist[a][b][k] + 1;
				que.push(make_pair(make_pair(tmp, b), k ^ 1));
			}
		}
		else {
			int tmp;
			tmp = (b + dB) % N;
			if (dist[a][tmp][k ^ 1] == 0) {
				dist[a][tmp][k ^ 1] = dist[a][b][k] + 1;
				que.push(make_pair(make_pair(a, tmp), k ^ 1));
			}
			tmp = (b - dB + N) % N;
			if (dist[a][tmp][k ^ 1] == 0) {
				dist[a][tmp][k ^ 1] = dist[a][b][k] + 1;
				que.push(make_pair(make_pair(a, tmp), k ^ 1));
			}
		}
	}

	return -1;
}

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

	cin >> N >> A >> B >> dA >> dB;
	A--; B--;

	int ans = bfs();
	if (ans < 0) cout << "Evil Galazy";
	else cout << ans;
}