BOJ 17837 : 새로운 게임 2

#BOJ 17837 : 새로운 게임 2

17837번: 새로운 게임 2

#풀이

구현문제는 너무 실수가 많네요.....

 

문제는 쉬운데... 

 

일단 저는 체스판을 3차원벡터로 선언하여 체스말들을 추가할 수 있게 만들었습니다.

 

그리고 방향으로 보고 체스판의 색깔을 구분합니다.

 

파란색 또는 체스판 바깥

조건에 맞게 파란색일 때 방향을 바꿔주고 가야할 칸의 색깔을 판별합니다.

 

빨간색

내가 움직이는 말을 순서를 바꾼다.

순서를 바꿀 때는 deque를 사용했다.

 

빈칸

그냥 움직인다.

 

여기서 중요한게 항상 움직일 때마다 체스말들의 벡터를 최신화해줘야 한다.

 

#코드

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

int n, k;
int arr[13][13];
tuple<int, int, int>v[11];
int ans = 0;
vector<vector<vector<int>>>v2(13, vector<vector<int>>(13, vector<int>(0)));

bool Check() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (v2[i][j].size() >= 4)
				return 1;
		}
	}
	return 0;

}

void move(tuple<int, int, int> A, int num) {
	int x, y, d;
	tie(x, y, d) = A;

	if (d == 1) // 오른쪽으로
	{
		if (arr[x][y + 1] == 2 || y == n)//파란색
		{
			if (arr[x][y - 1] == 2 || y - 1 <1) {
				v[num] = { x,y,2 };
				return;
			}
			else {
				v[num] = { x,y,2 };
				move({ x,y,2 }, num);
			}
		}
		else if (arr[x][y + 1] == 1) //빨간색
		{
			deque<int> dq;
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx,yy + 1, ddir };
					dq.push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
			while (!dq.empty()) {
				int c = dq.back(); dq.pop_back();
				v2[x][y + 1].push_back(c);
			}
		}
		
		else if(arr[x][y+1] == 0) // 빈 칸
		{
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx,yy + 1, ddir };
					v2[x][y + 1].push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
		}
		

	}

	else if (d == 2)//왼쪽으로
	{
		if (arr[x][y - 1] == 2 || y == 1)//파란색
		{
			if (arr[x][y + 1] == 2 || y + 1 > n) {
				v[num] = { x,y,1 };
				return;
			}
			else {
				v[num] = { x,y,1 };
				move({ x,y,1 }, num);
			}
		}
		else if (arr[x][y - 1] == 1) //빨간색
		{
			deque<int> dq;
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx,yy - 1, ddir };
					dq.push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
			while (!dq.empty()) {
				int c = dq.back(); dq.pop_back();
				v2[x][y - 1].push_back(c);
			}
		}
		else if (arr[x][y - 1] == 0) // 빈 칸
		{
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx,yy - 1, ddir };
					v2[x][y - 1].push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
		}
	}

	else if (d == 3) //위로
	{
		if (arr[x - 1][y] == 2 || x == 1)//파란색
		{
			if (arr[x + 1][y] == 2 || x + 1 > n) {
				v[num] = { x,y,4 };
				return;
			}
			else {
				v[num] = { x,y,4 };
				move({ x,y,4 }, num);
			}
		}
		else if (arr[x-1][y] == 1) //빨간색
		{
			deque<int> dq;
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx-1,yy, ddir };
					dq.push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
			while (!dq.empty()) {
				int c = dq.back(); dq.pop_back();
				v2[x-1][y].push_back(c);
			}
		}
		else if(arr[x-1][y] == 0) // 빈 칸
		{
			bool flag = 0;
			for (int i = 0; i < v2[x][y].size(); i++) {
				if (v2[x][y][i] == num)
					flag = 1;
				if (flag) {
					int xx, yy, ddir;
					tie(xx, yy, ddir) = v[v2[x][y][i]];
					v[v2[x][y][i]] = { xx-1,yy, ddir };
					v2[x-1][y].push_back(v2[x][y][i]);
					v2[x][y].erase(v2[x][y].begin() + i);
					i--;
				}
			}
		}
	}

	else // 아래로
	{
		if (arr[x + 1][y] == 2 || x == n)//파란색
		{
			if (arr[x - 1][y] == 2 || x - 1 < 1) {
				v[num] = { x,y,3 };
				return;
			}
			else {
				v[num] = { x,y,3 };
				move({ x,y,3 }, num);
			}
		}
	else if (arr[x+1][y] == 1) //빨간색
	{
		deque<int> dq;
		bool flag = 0;
		for (int i = 0; i < v2[x][y].size(); i++) {
			if (v2[x][y][i] == num)
				flag = 1;
			if (flag) {
				int xx, yy, ddir;
				tie(xx, yy, ddir) = v[v2[x][y][i]];
				v[v2[x][y][i]] = { xx+1,yy, ddir };
				dq.push_back(v2[x][y][i]);
				v2[x][y].erase(v2[x][y].begin() + i);
				i--;
			}
		}
		while (!dq.empty()) {
			int c = dq.back(); dq.pop_back();
			v2[x+1][y].push_back(c);
		}
	}
	
	else if (arr[x+1][y] == 0) // 빈 칸
	{
		bool flag = 0;
		for (int i = 0; i < v2[x][y].size(); i++) {
			if (v2[x][y][i] == num)
				flag = 1;
			if (flag) {
				int xx, yy, ddir;
				tie(xx, yy, ddir) = v[v2[x][y][i]];
				v[v2[x][y][i]] = { xx+1,yy, ddir };
				v2[x+1][y].push_back(v2[x][y][i]);
				v2[x][y].erase(v2[x][y].begin() + i);
				i--;
			}
		}
	}
	}
}
void solved(int cur) {
	if (cur > 1000)
	{
		ans = -1;
		return;
	}

	

	for (int i = 1; i <= k; i++) {
		move(v[i], i);
		if (Check()) {
			ans = cur;
			return;
		}
	}
	solved(cur + 1);
	
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= k; i++) {
		int x, y, dir;
		cin >> x >> y >> dir;
		v[i]= { x,y,dir };
		v2[x][y].push_back(i);
	}

	solved(1);

	cout << ans << '\n';
	return 0;
}