[백준] 17837 - 새로운 게임 2

17837 백준 새로운 게임 2

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

예제 입력 1

4 4

0 0 2 0

0 0 1 0

0 0 1 2

0 2 0 0

2 1 1

3 2 3

2 2 1

4 1 2

예제 출력 1

-1

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

int N, K;
struct horse {
	int row, col, dir;
};
// 1. <-, 2. ->, 3. ^, 4. v;
const int dx[] = { 0, 0, -1, 1 };
const int dy[] = { 1, -1, 0, 0 };
const int newDir[] = { 1, 0, 3, 2 };

// (게임 판에 어떤 말이 올라와 있는지에 대한 정보, 색)
vector<vector<pair<vector<int>, int>>> horseBoard;
// 말에 대한 정보
vector<horse> horseVec;

int moveHorse(int horseNum) {
	int curRow = horseVec[horseNum].row;
	int curCol = horseVec[horseNum].col;
	int nextRow = curRow + dx[horseVec[horseNum].dir];
	int nextCol = curCol + dy[horseVec[horseNum].dir];

	if (nextRow < 0 || nextRow >= N ||
		nextCol < 0 || nextCol >= N ||
		horseBoard[nextRow][nextCol].second == 2) {
		horseVec[horseNum].dir = newDir[horseVec[horseNum].dir];

		nextRow = curRow + dx[horseVec[horseNum].dir];
		nextCol = curCol + dy[horseVec[horseNum].dir];

		if (nextRow < 0 || nextRow >= N ||
			nextCol < 0 || nextCol >= N ||
			horseBoard[nextRow][nextCol].second == 2)
			return horseBoard[curRow][curCol].first.size();
	}

	vector<int>& cur = horseBoard[curRow][curCol].first;
	vector<int>& next = horseBoard[nextRow][nextCol].first;

	auto findIter = find(cur.begin(), cur.end(), horseNum);
	if (horseBoard[nextRow][nextCol].second == 1)
		reverse(findIter, cur.end());

	for (auto iter = findIter; iter != cur.end(); iter++) {
		horseVec[*iter].row = nextRow;
		horseVec[*iter].col = nextCol;
		next.push_back(*iter);
	}

	cur.erase(findIter, cur.end());
	return next.size();
}

int main(){
	/* INIT Phase */
	cin >> N >> K;
	horseBoard.resize(N);
	for (int i = 0; i < N; i++) horseBoard[i].resize(N);

	horseVec.resize(K);
	
	int color;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> color;
			horseBoard[i][j].second = color;
		}
	}

	int row, col, dir;
	for (int i = 0; i < K; ++i) {
		cin >> row >> col >> dir;
		horseVec[i].row = row - 1;
		horseVec[i].col = col - 1;
		horseVec[i].dir = dir - 1;
		horseBoard[row - 1][col - 1].first.push_back(i);
	}

	/* SOLVE Phase */
	for (int i = 1; i <= 1000; i++) {
		for (int j = 0; j < K; j++) {
			if (moveHorse(j) >= 4) {
				cout << i;
				return 0;
			}
		}
	}

	cout << -1;
	return 0;
}