[백준/BOJ] 백준 17837번 : 새로운 게임 2

www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

vector<pair<int, int>> h_board[13][13]에 해당 위치에 속한 말의 번호와 뱡향을 말이 쌓이는 순서대로 저장하였고, vector<pair<pair<int, int>, int>> horse(11)를 통해 각 번호의 말의 위치와 방향을 저장햐여 문제를 해결했다.

 

코드

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

int n, k;
int board[13][13];
vector<pair<int, int>> h_board[13][13]; //말의 번호, 방향 저장
vector<pair<pair<int, int>, int>> horse(11); //각 번호의 말의 위치, 방향 저장
int dxdy[5][2] = { {0,0}, {0,1},{0,-1},{-1,0},{1,0} };

int Check()
{
	for (int i = 1; i <= k; i++)
	{
		if (h_board[horse[i].first.first][horse[i].first.second].size() >= 4)
			return true;
	}
	return false;
}

int Solve(int cnt)
{
	if (cnt > 1000)
		return -1;

	for (int i = 1; i <= k; i++)
	{
		pair<pair<int, int>, int> here = horse[i]; //위치, 방향저장
		pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dxdy[here.second][0], here.first.second + dxdy[here.second][1]), here.second);

		vector<pair<int, int>> heres; //해당 말 이상의 말들의 번호, 방향 저장
		for (int j = 0; j < h_board[here.first.first][here.first.second].size(); j++)
		{
			if (h_board[here.first.first][here.first.second][j].first == i)
			{
				for (int k = j; k < h_board[here.first.first][here.first.second].size(); k++)
					heres.push_back(h_board[here.first.first][here.first.second][k]);

				h_board[here.first.first][here.first.second].erase(h_board[here.first.first][here.first.second].begin() + j, h_board[here.first.first][here.first.second].end());
				break;
			}
		}

		if (there.first.first >= 1 && there.first.first <= n && there.first.second >= 1 && there.first.second <= n)
		{
			//이동하려는 칸이 흰색일때
			if (board[there.first.first][there.first.second] == 0)
			{
				for (int j = 0; j < heres.size(); j++)
				{
					h_board[there.first.first][there.first.second].push_back(heres[j]);
					horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
				}
			}

			//이동하려는 칸이 빨간색일때
			if (board[there.first.first][there.first.second] == 1)
			{
				reverse(heres.begin(), heres.end());
				for (int j = 0; j < heres.size(); j++)
				{
					h_board[there.first.first][there.first.second].push_back(heres[j]);
					horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
				}
			}

			//이동하려는 칸이 파란색일때
			if (board[there.first.first][there.first.second] == 2)
			{
				if (there.second == 1)
				{
					there = make_pair(make_pair(here.first.first + dxdy[2][0], here.first.second + dxdy[2][1]), 2);
					heres[0].second = 2;
				}

				else if (there.second == 2)
				{
					there = make_pair(make_pair(here.first.first + dxdy[1][0], here.first.second + dxdy[1][1]), 1);
					heres[0].second = 1;
				}

				else if (there.second == 3)
				{
					there = make_pair(make_pair(here.first.first + dxdy[4][0], here.first.second + dxdy[4][1]), 4);
					heres[0].second = 4;
				}

				else if (there.second == 4)
				{
					there = make_pair(make_pair(here.first.first + dxdy[3][0], here.first.second + dxdy[3][1]), 3);
					heres[0].second = 3;
				}

				if (there.first.first >= 1 && there.first.first <= n && there.first.second >= 1 && there.first.second <= n)
				{
					if (board[there.first.first][there.first.second] == 0)
					{
						for (int j = 0; j < heres.size(); j++)
						{
							h_board[there.first.first][there.first.second].push_back(heres[j]);
							horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
						}
					}

					else if (board[there.first.first][there.first.second] == 1)
					{
						reverse(heres.begin(), heres.end());
						for (int j = 0; j < heres.size(); j++)
						{
							h_board[there.first.first][there.first.second].push_back(heres[j]);
							horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
						}
					}

					else if (board[there.first.first][there.first.second] == 2)
					{
						for (int j = 0; j < heres.size(); j++)
						{
							h_board[here.first.first][here.first.second].push_back(heres[j]);
							horse[heres[j].first] = make_pair(make_pair(here.first.first, here.first.second), heres[j].second);
						}
					}
				}

				else
				{
					for (int j = 0; j < heres.size(); j++)
					{
						h_board[here.first.first][here.first.second].push_back(heres[j]);
						horse[heres[j].first] = make_pair(make_pair(here.first.first, here.first.second), heres[j].second);
					}
				}
			}
		}

		else //이동하려는 칸이 범위 밖일때
		{
			if (there.second == 1)
			{
				there = make_pair(make_pair(here.first.first + dxdy[2][0], here.first.second + dxdy[2][1]), 2);
				heres[0].second = 2;
			}

			else if (there.second == 2)
			{
				there = make_pair(make_pair(here.first.first + dxdy[1][0], here.first.second + dxdy[1][1]), 1);
				heres[0].second = 1;
			}

			else if (there.second == 3)
			{
				there = make_pair(make_pair(here.first.first + dxdy[4][0], here.first.second + dxdy[4][1]), 4);
				heres[0].second = 4;
			}

			else if (there.second == 4)
			{
				there = make_pair(make_pair(here.first.first + dxdy[3][0], here.first.second + dxdy[3][1]), 3);
				heres[0].second = 3;
			}

			if (there.first.first >= 1 && there.first.first <= n && there.first.second >= 1 && there.first.second <= n)
			{
				if (board[there.first.first][there.first.second] == 0)
				{
					for (int j = 0; j < heres.size(); j++)
					{
						h_board[there.first.first][there.first.second].push_back(heres[j]);
						horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
					}
				}

				else if (board[there.first.first][there.first.second] == 1)
				{
					reverse(heres.begin(), heres.end());
					for (int j = 0; j < heres.size(); j++)
					{
						h_board[there.first.first][there.first.second].push_back(heres[j]);
						horse[heres[j].first] = make_pair(make_pair(there.first.first, there.first.second), heres[j].second);
					}
				}

				else if (board[there.first.first][there.first.second] == 2)
				{
					for (int j = 0; j < heres.size(); j++)
					{
						h_board[here.first.first][here.first.second].push_back(heres[j]);
						horse[heres[j].first] = make_pair(make_pair(here.first.first, here.first.second), heres[j].second);
					}
				}
			}

			else
			{
				for (int j = 0; j < heres.size(); j++)
				{
					h_board[here.first.first][here.first.second].push_back(heres[j]);
					horse[heres[j].first] = make_pair(make_pair(here.first.first, here.first.second), heres[j].second);
				}
			}
		}
		if (Check())
			return cnt;
	}

	return Solve(cnt + 1);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	for (int i = 1; i <= k; i++)
	{
		int r, c, d;

		cin >> r >> c >> d;
		h_board[r][c].push_back(make_pair(i, d));
		horse[i] = make_pair(make_pair(r, c), d);
	}

	cout << Solve(1);
}