백준 17837번 : 새로운 게임2

sol : 81' 40''

• 수행 시간 : 4ms -> 0ms
• 메모리 : 2032KB

Learnings

• 다음엔 1시간 이내로 풀어보자.

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

#define MAX_N 13
#define WHITE 0
#define RED 1
#define BLUE 2

#define RIGHT 1
#define LEFT 2
#define UP 3
#define DOWN 4

int n, k, turn;
bool impossible, finish;
// 우, 좌, 상, 하
const int ds[5][2] = {
	{0, 0},
	{0, 1},
	{0, -1},
	{-1, 0},
	{1, 0}
};

struct Horse {
	int i;
	int j;
	int dir;

	Horse() {}
	Horse(int _i, int _j, int _dir) :
		i(_i), j(_j), dir(_dir) { }
};

vector<int> horseGrid[MAX_N][MAX_N];
int boardGrid[MAX_N][MAX_N];
vector<Horse> horses;
vector<bool> moved;

void Init() {
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> boardGrid[i][j];
		}
	}

	horses.resize(k + 1);
	for (int i = 1; i <= k; i++) {
		int r, c, dir;
		cin >> r >> c >> dir;
		horseGrid[r][c].push_back(i);
		horses[i] = Horse(r, c, dir);
	}

	moved.resize(k + 1);
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

int Oppos(int dir) {
	if (dir == LEFT) return RIGHT;
	if (dir == RIGHT) return LEFT;
	if (dir == UP) return DOWN;
	if (dir == DOWN) return UP;
	return -1;
}

void Move() {
	for (int h = 1; h <= k; h++) {
		moved[h] = false;

		int ci = horses[h].i, cj = horses[h].j, cd = horses[h].dir;
		int ni = ci + ds[cd][0], nj = cj + ds[cd][1];

		// 체스판을 벗어나거나 파란색인 경우
		if (!InGrid(ni, nj) || boardGrid[ni][nj] == BLUE) {
			cd = Oppos(cd);
			ni = ci + ds[cd][0], nj = cj + ds[cd][1];
			horses[h].dir = cd;
			if (!InGrid(ni, nj) || boardGrid[ni][nj] == BLUE) continue;
		}

		vector<int> stayer, mover;
		for (int i = 0; i < horseGrid[ci][cj].size(); i++) {
			if (horseGrid[ci][cj][i] != h) {
				stayer.push_back(horseGrid[ci][cj][i]);
			}
			else {
				for (int j = i; j < horseGrid[ci][cj].size(); j++) {
					mover.push_back(horseGrid[ci][cj][j]);
				}
				break;
			}
		}
		horseGrid[ci][cj] = stayer;

		// 흰색인 경우
		if (boardGrid[ni][nj] == WHITE) {
			for (int i = 0; i < mover.size(); i++) {
				horseGrid[ni][nj].push_back(mover[i]);
				horses[mover[i]].i = ni, horses[mover[i]].j = nj;
			}
		}

		// 빨간색인 경우
		else if (boardGrid[ni][nj] == RED) {
			for (int i = mover.size() - 1; i >= 0; i--) {
				horseGrid[ni][nj].push_back(mover[i]);
				horses[mover[i]].i = ni, horses[mover[i]].j = nj;
			}
		}

		moved[h] = true;
		if (horseGrid[ni][nj].size() >= 4) {
			finish = true;
			return;
		}
	}
}

bool Impossible() {
	impossible = true;
	for (int i = 1; i <= k; i++) {
		if (moved[i]) impossible = false;
	}

	return impossible;
}

int main() {
	Init();

	while (++turn <= 1000) {
		Move();

		if (finish) {
			cout << turn;
			return 0;
		}

		if (Impossible()) break;
	}
	
	cout << -1;

	return 0;
}