[백준/c++] 17837 새로운 게임 2

문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 1 ) 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 2) 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

3) 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 4) 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

제한

• 4 ≤ N ≤ 12
• 4 ≤ K ≤ 10

 

구현해야할 조건

말은 계속 쌓여가는것 자료구조 vector를 이용해서 문제를 해결할 수 있다고 생각을 했다. 그리고 턴이 진행되는 것은 1번 말부터 k번 말까지 순서대로 이동을 시키는 것이기 때문에, 처음에 queue를 이용해서 순차적으로 풀기로 했지만 그렇게는 해서는 queue로 sort를 해주어야 하고 복잡하기에 배열을 사용해 값들을 집어넣어주었고, queue를 쓰면서 가장 큰 문제는 위에 얹혀있는 말이 다 같이 이동을 하는데 이미 queue에 위치를 집어넣어준 상태라 바꿔주기 힘들다는 점이다. 그점을 생각하면 매번 이동마다 바꿔줘야하는 방식으로 해야하는데 순차적으로 진행도 하니까 배열이 적당하다.

이동시에 문제인데, 초반에는 1개 초과인 말과 1개인 말을 나눠서 했지만 이렇게 하면 문제가 매우 복잡해진다.
1개 초과인 말에서 범위 안에 있는 것 없는것, 그리고 다음칸이 파란색인지, 파란색칸이면 다음 칸이 파란색이 아닌지 맞는지 이것저것 확인할 것이 많은데, 단순하게 범위로만 나누고, 1개인지 1개 초과인지 나누는 것은 동일하게 처리를 할 수 있다. 범위가 작기 때문에 가능하다. 문제에 나온 대로 구현을 해주면 된다.

 

 

code

 

#include<iostream>
#include<vector>

#define MAX 12
#define Chess_MAX 10

using namespace std;

typedef struct{
	int y;
	int x;
	int dir;
}Horse;

const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,-1,1}; // right, left, up, down

int n,k,res;
int wall[MAX][MAX];
vector<int> board[MAX][MAX]; // 숫자를 넣을 이유가 없지 왜냐면, horse 배열에서 처리 
Horse horse[Chess_MAX];

int find_location(int y, int x, int index)
{
	for(int i = 0; i < board[y][x].size(); i++)
	{
		if(board[y][x][i] == index) // 체스를 옮겨줄 시작 위치를 구하는 방법 
			return i;
	}
}

int delete_num(int y, int x, int num)
{
	int cnt = 0;
		
	for(int i = board[y][x].size() - 1; i >= 0; i--)
	{
		if(board[y][x][i] == num) // 체스 말을 삭제해줄 범위까지 구하는 방법 
			break;
		cnt++;
	}
	return cnt+1; // <= cnt 사용해도 되지만 항상 하던 편의를 위해 바꿔주었고 
}

int reverse_rotate(int d)
{
	if(d == 0) return 1;
	else if(d == 1) return 0;
	else if(d == 2) return 3;
	else if(d == 3) return 2; // 파란색 또는 범위를 벗어나면 방향을 바꿔주는  
} 

void moving(int y, int x, int ny, int nx, int num, int loc, int wall_color)
{
	if(wall_color == 0) // 흰색 
	{
		for(int i = loc; i < board[y][x].size(); i++) // 찾은 위치 loc 
		{
			board[ny][nx].push_back(board[y][x][i]); // 하나씩 push 
			int index = board[y][x][i]; // index 몇번째 애 
			horse[index].y = ny; // 숫자 바꿔주기 
			horse[index].x = nx;
		}
		// 값을 지워줘야지?
		
		int delete_loc = delete_num(y,x,num); // 그만큼 pop_back()을 해주면 된다. 

		for(int i = 0; i < delete_loc; i++)
		{
			board[y][x].pop_back();
		}	
	}
	else if(wall_color == 1) // 빨간
	{
		for(int i = board[y][x].size() - 1; i >= loc; i--)
		{
			board[ny][nx].push_back(board[y][x][i]);
			int index = board[y][x][i];
			horse[index].y = ny;
			horse[index].x = nx;
		}
		
		int delete_loc = delete_num(y,x,num);
		
		for(int i = 0; i < delete_loc; i++)
		{
			board[y][x].pop_back();
		}
		
	}
	else if(wall_color == 2) // 파랑
	{
		  //파랑에 파랑을 만나면?
		int rd = reverse_rotate(horse[num].dir);
		horse[num].dir = rd; // 방향만 바꿔주면 되는것 
		
		int rnx = x + dx[rd];
		int rny = y + dy[rd];
		
		if(0 <= rnx && rnx < n && 0 <= rny && rny < n)
		{
			if(wall[rny][rnx] != 2) // 2가 아니면
			{
				moving(y,x,rny,rnx,num,loc,wall[rny][rnx]); // 파랑색 다음 칸으로 이동을 해야하는 것, 내가 이거 구현하다가 길어졌다. 
			} 
		}
	}
}

bool chk_state()
{
	for(int i = 0; i < k; i++)
	{
		int y = horse[i].y;
		int x = horse[i].x;
		if(board[y][x].size() >= 4)
			return true;
	}
	
	return false;
} 

int main()
{
	cin >> n >> k;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> wall[i][j];
		}
	}
	
	for(int i = 0; i < k; i++)
	{
		int y, x, d;
		cin >> y>> x>> d; // x--, y--, d-- 

		horse[i] = {y-1,x-1,d-1};
		board[y-1][x-1].push_back(i); // number가 들어가게 된다. 
	}
	
	bool chk = false;
	int time = 0;
	
	while(1)
	{
		if(time > 1000)
			break; // base condition
			
		for(int i = 0; i < k; i++)
		{
			int y = horse[i].y;
			int x = horse[i].x;
			int dir = horse[i].dir;
			
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			
			int temp_loc = find_location(y,x,i);
			
			if(0 <= nx && nx < n && 0 <= ny && ny < n)
			{
				//범위 안에 들어오면 옮겨줘라
				moving(y,x,ny,nx,i,temp_loc,wall[ny][nx]); 
			}
			else
			{
				moving(y,x,ny,nx,i,temp_loc,2); // 범위 밖이면 파란색이랑 똑같다. 
			}
			
			if(chk_state() == true)
			{
				chk = true;
				break;
			}

		}
		if(chk)
			break;
			
		time++;	
	}

	if(chk)
		cout << time + 1;
	else
		cout << -1;
	
	return 0;
}