백준 - 원판 돌리기 (17837번)

백준 - 원판 돌리기 (17837번)

벡터 배열을 생성하고, push_back 정도만 잘 해주면 풀 수 있는 문제이다.

게임이 끝나는 조건이 턴을 진행하는 중 체스가 4개 이상 쌓이면 종료되기 때문에, 체스를 움직일 때마다 체크해줘야한다.(이 부분에서 실수해서 30분동안 헤맸다;)

코드는 아래와 같다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

typedef struct __chess_info {
	int row;
	int col;
	int dir;
	int idx;
} chess_info;

int n, k;

int rowDir[4] = { 0, 0, -1, 1 };
int colDir[4] = { 1, -1, 0, 0 };

int map_color[16][16];
vector<chess_info> chess_map[16][16];
chess_info chess[16];

void print_map(const char *s)
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("(%d) Map[%d][%d] : ", map_color[i][j], i, j);
			for (int k = 0; k < chess_map[i][j].size(); k++) 
				printf("[%d]", chess_map[i][j][k].idx + 1);
			printf("\n");
		}
	}
	
}


bool end_check()
{
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (chess_map[i][j].size() >= 4)
				return true;

	return false;
}

bool is_safe(int row, int col)
{
	if (row < 0 || col < 0 || row > n - 1 || col > n - 1)
		return false;
	if (map_color[row][col] == 2)
		return false;
	return true;
}
bool solve()
{
	for (int i = 0; i < k; i++) {
		vector<chess_info>& from = chess_map[chess[i].row][chess[i].col];

		int nrow = chess[i].row + rowDir[chess[i].dir];
		int ncol = chess[i].col + colDir[chess[i].dir];
		

		if (!is_safe(nrow, ncol)) {
			if (chess[i].dir == 0 || chess[i].dir == 2)
				chess[i].dir += 1;
			else
				chess[i].dir -= 1;
			nrow = chess[i].row + rowDir[chess[i].dir];
			ncol = chess[i].col + colDir[chess[i].dir];
			if (!is_safe(nrow, ncol))
				continue;
		}

		vector<chess_info>& to = chess_map[nrow][ncol];
		int cur = 0;
		int size = from.size();
		for (int j = 0; j < size; j++) {
			if (chess[i].idx == from[j].idx) {
				cur = j;
				break;
			}
		}

		if (map_color[nrow][ncol] == 0) {
			for (int j = cur; j < size; j++) {
				to.push_back(chess[from[j].idx]);
				chess[from[j].idx].row = nrow;
				chess[from[j].idx].col = ncol;
			}

			while (1) {
				if (from.empty())
					break;
				chess_info target = from.back();
				from.pop_back();
				if (chess[i].idx == target.idx)
					break;
			}
		}
		else {
			for (int j = size - 1; j >= cur; j--) {
				to.push_back(chess[from[j].idx]);
				chess[from[j].idx].row = nrow;
				chess[from[j].idx].col = ncol;
			}

			while (1) {
				if (from.empty())
					break;
				chess_info target = from.back();
				from.pop_back();
				if (chess[i].idx == target.idx)
					break;
			}
		}
		if (end_check())
			return true;
	}
	return false;
}
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; i++) 
		for(int j=0;j<n;j++)
			cin >> map_color[i][j];
	
	for (int i = 0; i < k; i++) {
		cin >> chess[i].row >> chess[i].col >> chess[i].dir;
		chess[i].row--; chess[i].col--; chess[i].dir--; chess[i].idx = i;
		chess_map[chess[i].row][chess[i].col].push_back(chess[i]);
	}

	int turn = 1;
	while (1) {
		if (turn > 1000)
			break;

		if (solve())
			break;

		turn++;
	}

	int answer = turn > 1000 ? -1 : turn;
	cout << answer << "\n";

	return 0;
}