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

www.acmicpc.net/problem/17780

17780번: 새로운 게임

vector<int> board[13][13]; 에 해당 칸의 위치한 말들(아래서부터 위 순서로)을 저장하고, vector<horse> info(11);에 각 번호의 말의 위치, 방향 저장하고, number번 말을 움직이는 함수 Move(int number)를 구현하여 문제를 해결했다.

 

코드

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

int n, k;
int color[13][13];
vector<int> board[13][13]; //해당 칸의 위치한 말들(아래서부터 위 순서로)
int cnt = 0;
struct horse {
	int x;
	int y;
	int dir;
};
vector<horse> info(11); //각 번호의 말의 위치,방향 저장
int dxdy[5][2] = { {0,0},{0,1},{0,-1},{-1,0},{1,0} };

bool Move(int number)
{
	pair<int, int> here = make_pair(info[number].x, info[number].y);
	int here_dir = info[number].dir;
	vector<int> here_up_number; //number포함 number말 위의 말들

	//가장 아래에 있는 말만 이동할 수 있다
	if (board[here.first][here.second][0] != number)
		return false;

	for (int i = 0; i < board[here.first][here.second].size(); i++)
		here_up_number.push_back(board[here.first][here.second][i]);
	board[here.first][here.second].clear();

	pair<int, int> there = make_pair(here.first + dxdy[here_dir][0], here.second + dxdy[here_dir][1]);

	//이동하려는 칸인 범위를 벗어나거나 파란색일때
	if ((there.first <= 0 || there.first > n || there.second <= 0 || there.second > n) || color[there.first][there.second] == 2)
	{
		pair<int, int> next_there;
		int next_dir;

		if (here_dir == 1)
			next_dir = 2;
		else if (here_dir == 2)
			next_dir = 1;
		else if (here_dir == 3)
			next_dir = 4;
		else if (here_dir == 4)
			next_dir = 3;

		next_there = make_pair(here.first + dxdy[next_dir][0], here.second + dxdy[next_dir][1]);

		//방향을 바꿔서 가는 칸도 범위를 넘어가거나 파란색일때
		if ((next_there.first <= 0 || next_there.first > n || next_there.second <= 0 || next_there.second > n) || color[next_there.first][next_there.second] == 2)
		{
			info[here_up_number[0]].dir = next_dir;
			for (int i = 0; i < here_up_number.size(); i++)
			{
				board[here.first][here.second].push_back(here_up_number[i]);

				info[here_up_number[i]] = { here.first,here.second,info[here_up_number[i]].dir };
			}

			if (board[here.first][here.second].size() >= 4)
				return true;
		}

		//방향을 바꿔서 이동하려는 칸이 흰색일때
		else if (color[next_there.first][next_there.second] == 0)
		{
			info[here_up_number[0]].dir = next_dir;
			for (int i = 0; i < here_up_number.size(); i++)
			{
				board[next_there.first][next_there.second].push_back(here_up_number[i]);

				info[here_up_number[i]] = { next_there.first,next_there.second,info[here_up_number[i]].dir };
			}

			if (board[next_there.first][next_there.second].size() >= 4)
				return true;
		}

		//방향을 바꿔서 이동하려는 칸이 빨강색일때
		else if (color[next_there.first][next_there.second] == 1)
		{
			info[here_up_number[0]].dir = next_dir;
			reverse(here_up_number.begin(), here_up_number.end());

			for (int i = 0; i < here_up_number.size(); i++)
			{
				board[next_there.first][next_there.second].push_back(here_up_number[i]);

				info[here_up_number[i]] = { next_there.first,next_there.second,info[here_up_number[i]].dir };
			}

			if (board[next_there.first][next_there.second].size() >= 4)
				return true;
		}
	}

	//이동하려는 칸이 흰색일때
	else if (color[there.first][there.second] == 0)
	{
		for (int i = 0; i < here_up_number.size(); i++)
		{
			board[there.first][there.second].push_back(here_up_number[i]);

			info[here_up_number[i]] = { there.first,there.second,info[here_up_number[i]].dir };
		}

		if (board[there.first][there.second].size() >= 4)
			return true;
	}

	//이동하려는 칸이 빤강색일때
	else if (color[there.first][there.second] == 1)
	{
		reverse(here_up_number.begin(), here_up_number.end());

		for (int i = 0; i < here_up_number.size(); i++)
		{
			board[there.first][there.second].push_back(here_up_number[i]);

			info[here_up_number[i]] = { there.first,there.second,info[here_up_number[i]].dir };
		}

		if (board[there.first][there.second].size() >= 4)
			return true;
	}

	return false;
}

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;

			color[i][j] = input;
		}

	for (int i = 1; i <= k; i++)
	{
		int x, y, dir;

		cin >> x >> y >> dir;

		board[x][y].push_back(i); //(x,y)위치의 말 저장
		info[i] = { x,y,dir }; //i번 말의 정보 저장
	}

	while (1)
	{
		cnt++;

		if (cnt > 1000)
			break;

		for (int i = 1; i <= k; i++)
		{
			bool finish = Move(i);

			if (finish == true)
			{
				cout << cnt;

				return 0;
			}
		}
	}

	cout << -1;

	return 0;
}