백준 17837번 _ 새로운 게임 2

https://www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

 

풀이방법

시뮬레이션 문제다보니 생각할거리가 정말 많다.

 

1. 내 위에 쌓여있는 말은 무엇이고, 내 밑에 쌓여있는 말은 무엇인가?

 

2. 갈곳이 흰색일때

 

3. 갈곳이 빨간색일때

 

4. 갈곳이 파란색 or 범위를 넘어설때

 4. 1) 방향을 반대로 바꿔서 갔을때 그곳이 흰색일때

 4. 2) 방향을 반대로 바꿔서 갔을때 그곳이 빨간색일때

 4. 3) 방향을 반대로 바꿔서 갔을때 그곳이 파란색일때

 

5. 위의 모든것을 합쳐 구현

 

위의 것들을 다 고려해서 풀어야 한다. 

 

---

구현방법

1. 내 위에 쌓여있는 말은 무엇이고, 내 밑에 쌓여있는 말은 무엇인가?

void divideChess(int y, int x, int chessNum, vector<int>&remainC, vector<int>&moveC)
{
	for (int i = 0; i < (int)board[y][x].size(); i++)
	{
		if (chessNum == board[y][x][i])
		{
			remainC.assign(begin(board[y][x]), begin(board[y][x]) + i);
			moveC.assign(begin(board[y][x]) + i, end(board[y][x]));
			break;
		}
	}
}

 

2. 갈곳이 흰색일때

void colorWhite(int y, int x, int ny, int nx,int dir, vector<int> moveC, vector<int> remainC, int chessNum)
{
	board[ny][nx].insert(end(board[ny][nx]), begin(moveC), end(moveC));
	for (auto& ele : moveC)
		chessPoint[ele] = Chess(ny, nx, chessPoint[ele].dir);
	chessPoint[chessNum] = Chess(ny, nx, dir);
	board[y][x] = move(remainC);
}

 

3. 갈곳이 빨간색일때

void colorRed(int y, int x, int ny, int nx,int dir,  vector<int>moveC, vector<int> remainC, int chessNum)
{
	reverse(begin(moveC), end(moveC));
	board[ny][nx].insert(end(board[ny][nx]), begin(moveC), end(moveC));
	for (auto& ele : moveC)
		chessPoint[ele] = Chess(ny, nx, chessPoint[ele].dir);
	chessPoint[chessNum] = Chess(ny, nx, dir);
	board[y][x] = move(remainC);
}

 

4. 갈곳이 파란색 or 범위를 넘어설때

void colorBlue(int y, int x, int ny, int nx, int dir, vector<int>moveC, vector<int> remainC, int chessNum)
{
	dir = dirChange(dir);
	ny += (2 * dy[dir]);
	nx += (2 * dx[dir]);

	//바꿨는데도 범위를 넘거나 퍼랭이일 경우, 방향만 바꾸셈
	if (boardColor[ny][nx] == 2 || (ny > 0 && nx > 0 && nx <= N && ny <= N) == false)
	{
		chessPoint[chessNum] = Chess(y, x, dir);
		return;
	}
	else
	{
		//흰색
		if (boardColor[ny][nx] == 0)
			colorWhite(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//뻘갱이
		else if (boardColor[ny][nx] == 1)
			colorRed(y, x, ny, nx,dir,  moveC, remainC, chessNum);
	}
}

 

5. 위의 모든것을 합쳐 구현

void chessMove(int chessNum)
{
	auto cur = chessPoint[chessNum];
	int y = cur.y;
	int x = cur.x;
	int dir = cur.dir;

	//위에쌓인것과 쌓이지 않은것을 나눔
	vector<int>remainC;
	vector<int>moveC;
	divideChess(y, x, chessNum, remainC, moveC);

	//움직여보자
	int ny = y + dy[dir];
	int nx = x + dx[dir];

	if (ny > 0 && nx > 0 && ny <= N && nx <= N)
	{
		//흰색
		if (boardColor[ny][nx] == 0)
			colorWhite(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//뻘갱이
		else if (boardColor[ny][nx] == 1)
			colorRed(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//퍼랭이
		else
			colorBlue(y, x, ny, nx, dir, moveC, remainC, chessNum);
	}
	//퍼랭이로 취급
	else
		colorBlue(y, x, ny, nx, dir, moveC, remainC, chessNum);
}

 

---

 

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

class Chess
{
public:
	int y;
	int x;
	int dir;
	Chess()
	{}
	Chess(int y_in, int x_in, int dir_in)
		:y(y_in), x(x_in), dir(dir_in)
	{}
};


int boardColor[14][14];
vector<int>board[14][14];
map<int, Chess> chessPoint;
int dy[] = { 0,0,0,-1,1 };
int dx[] = { 0,1,-1,0,0 };
int N, K;

void Input()
{
	cin >> N >> K;
	int value;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> value;
			boardColor[i][j] = value;
		}
	}
	int y, x, dir;
	for (int i = 1; i <= K; i++)
	{
		cin >> y >> x >> dir;
		board[y][x].push_back(i);
		chessPoint[i] = Chess(y, x, dir);
	}
}

void divideChess(int y, int x, int chessNum, vector<int>&remainC, vector<int>&moveC)
{
	for (int i = 0; i < (int)board[y][x].size(); i++)
	{
		if (chessNum == board[y][x][i])
		{
			remainC.assign(begin(board[y][x]), begin(board[y][x]) + i);
			moveC.assign(begin(board[y][x]) + i, end(board[y][x]));
			break;
		}
	}
}

int dirChange(int dir)
{
	if (dir == 1)
		return 2;
	else if (dir == 2)
		return 1;
	else if (dir == 3)
		return 4;
	else
		return 3;
}

void colorWhite(int y, int x, int ny, int nx,int dir, vector<int> moveC, vector<int> remainC, int chessNum)
{
	board[ny][nx].insert(end(board[ny][nx]), begin(moveC), end(moveC));
	for (auto& ele : moveC)
		chessPoint[ele] = Chess(ny, nx, chessPoint[ele].dir);
	chessPoint[chessNum] = Chess(ny, nx, dir);
	board[y][x] = move(remainC);
}

void colorRed(int y, int x, int ny, int nx,int dir,  vector<int>moveC, vector<int> remainC, int chessNum)
{
	reverse(begin(moveC), end(moveC));
	board[ny][nx].insert(end(board[ny][nx]), begin(moveC), end(moveC));
	for (auto& ele : moveC)
		chessPoint[ele] = Chess(ny, nx, chessPoint[ele].dir);
	chessPoint[chessNum] = Chess(ny, nx, dir);
	board[y][x] = move(remainC);
}

void colorBlue(int y, int x, int ny, int nx, int dir, vector<int>moveC, vector<int> remainC, int chessNum)
{
	dir = dirChange(dir);
	ny += (2 * dy[dir]);
	nx += (2 * dx[dir]);

	//바꿨는데도 범위를 넘거나 퍼랭이일 경우, 방향만 바꾸셈
	if (boardColor[ny][nx] == 2 || (ny > 0 && nx > 0 && nx <= N && ny <= N) == false)
	{
		chessPoint[chessNum] = Chess(y, x, dir);
		return;
	}
	else
	{
		//흰색
		if (boardColor[ny][nx] == 0)
			colorWhite(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//뻘갱이
		else if (boardColor[ny][nx] == 1)
			colorRed(y, x, ny, nx,dir,  moveC, remainC, chessNum);
	}
}

void chessMove(int chessNum)
{
	auto cur = chessPoint[chessNum];
	int y = cur.y;
	int x = cur.x;
	int dir = cur.dir;

	//위에쌓인것과 쌓이지 않은것을 나눔
	vector<int>remainC;
	vector<int>moveC;
	divideChess(y, x, chessNum, remainC, moveC);

	//움직여보자
	int ny = y + dy[dir];
	int nx = x + dx[dir];

	if (ny > 0 && nx > 0 && ny <= N && nx <= N)
	{
		//흰색
		if (boardColor[ny][nx] == 0)
			colorWhite(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//뻘갱이
		else if (boardColor[ny][nx] == 1)
			colorRed(y, x, ny, nx,dir, moveC, remainC, chessNum);

		//퍼랭이
		else
			colorBlue(y, x, ny, nx, dir, moveC, remainC, chessNum);
	}
	//퍼랭이로 취급
	else
		colorBlue(y, x, ny, nx, dir, moveC, remainC, chessNum);
}

bool isSucess()
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (board[i][j].size() >= 4)
				return true;
	return false;
}

int solve()
{
	int cnt = 0;
	while (1)
	{
		//1000보다 턴이 큰경우
		if (cnt > 1000)
			return -1;
		for (int i = 1; i <= K; i++)
		{
			//말 move
			chessMove(i);
			//isSucess! (말이 4개이상 쌓여있다면)
			//만약에 isSucess함수가 true면 return cnt +1
			if (isSucess())
				return (cnt + 1);
		}
		cnt++;
	}
	return -1;
}

int main()
{
	Input();
	cout << solve();
	return 0;
}

 

---

후기

이 문제는 어떻게 풀지 깔끔하게 정리하고 풀어서 풀기 조금 수월했다.