새로운 게임 2 (feat. 백준, 17837번)

새로운 게임 2
https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/17837
#include <iostream>
#include <deque>
#include <stack>

using namespace std;

struct Chess {
	int x, y, d;
};
int N, K;
int dx[4], dy[4];
int maps[13][13];
stack<int> chesses_on_maps[13][13];
deque<int> tmp_store;
Chess chesses[11];

inline bool move_chess()
{
	for (int k = 1, x, y, d, nx, ny; k <= K; ++k) {
		x = chesses[k].x, y = chesses[k].y, d = chesses[k].d;
		nx = x + dx[d], ny = y + dy[d];
		if (1 <= nx && nx <= N && 1 <= ny && ny <= N) {
			if (maps[nx][ny] == 0)
				while (true) {
					auto& tmp_k = chesses_on_maps[x][y].top(); chesses_on_maps[x][y].pop();
					tmp_store.push_back(tmp_k);
					if (tmp_k == k)			break;
				}
			else if (maps[nx][ny] == 1)
				while (true) {
					auto& tmp_k = chesses_on_maps[x][y].top(); chesses_on_maps[x][y].pop();
					tmp_store.push_front(tmp_k);
					if (tmp_k == k)			break;
				}
			else {
				if (d == 0)			d = 1;
				else if (d == 1)	d = 0;
				else if (d == 2)	d = 3;
				else				d = 2;
				chesses[k].d = d;
				nx = x + dx[d], ny = y + dy[d];
				if (maps[nx][ny] != 2)		--k;
				continue;
			}
			while (!tmp_store.empty()) {
				auto& tmp_k = tmp_store.back();
				chesses_on_maps[nx][ny].push(tmp_k), tmp_store.pop_back();
				chesses[tmp_k].x = nx, chesses[tmp_k].y = ny;
			}
		}
		else {
			if (d == 0)			d = 1;
			else if (d == 1)	d = 0;
			else if (d == 2)	d = 3;
			else				d = 2;
			chesses[k].d = d;
			nx = x + dx[d], ny = y + dy[d];
			if (maps[nx][ny] != 2)		--k;
			continue;
		}
		if (chesses_on_maps[nx][ny].size() >= 4)
			return true;
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = dx[1] = 0, dx[2] = -1, dx[3] = 1;
	dy[0] = 1, dy[1] = -1, dy[2] = dy[3] = 0;
	cin >> N >> K;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			cin >> maps[ix][iy];
	for (int k = 1; k <= K; ++k)
		cin >> chesses[k].x >> chesses[k].y >> chesses[k].d, chesses[k].d -= 1, chesses_on_maps[chesses[k].x][chesses[k].y].push(k);

	auto result = 1;
	for (result; result <= 1000; ++result)
		if (move_chess())
			break;
	if (result > 1000)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}
// *&)*@*

1. 현재의 체스말들을 다음번 체스칸으로 옮길때, 다음번 체스칸이 흰색이냐 빨강이냐에 따라 deque의 앞부터 또는 뒤부터 삽입을 결정했습니다.
2. 옮길 체스칸에 이미 있는 말이 있다면, 그 위에 체스말들을 올려야 하므로, stack을 사용하면 그저 push만 이루어지면 됩니다.
3. 가장 시간이 오래 걸렸던 부분입니다. 게임의 종료 시점은 특정 체스칸에 체스말이 K개(체스말의 총 개수)가 아니라 4개 이상일 경우입니다.