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

www.acmicpc.net/problem/17837

17837번: 새로운 게임 2

문제

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

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

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

입력

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

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

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

출력

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

제한

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

 

풀이과정

1. 시뮬레이션으로 접근했다. (딱히 알고리즘적으로 생각나지 않았음..!)

2. g_chess벡터는 chess의 정보를 가진다 (현재 위치, 방향) 

 : 선언한 이유는 맵을 모두 체크하면서 체스의 순서대로 움직이는 것은 낭비이므로 바로 사용 할 수 있도록 선언함.

3. map은 체스판의 색을 담당하는 배열이다.

4. chessMap은 벡터의 배열로 각 위치에 체스의 갯수를 담당한다.

 : 모든 체스의 위치 중 같은 것은 4개 이상 찾는 것보다, 현 위치의 vector 사이즈를 체크 하는 것이 더 편하다고 생각함.

 

5. 시퀀스 마다 모든 체스가 순서대로 이동한다. (g_chess에 순서대로 담겨있다.)

6. 이동 할 체스판의 색에 맞게 동작을 취하면 된다. 내 위로 존재하는 체스는 모두 이동 시킨다.

   chessMap에 순서대로 담겨있다. index가 높은 것은 나보다 위에 있는 뜻이다.

   removeAndMove함수에서 현재 이동 할 밸류의 위치를 찾고, moveList에 넣어준다.

   moveList 포함 된 체스는 변경되는 위치로 업데이트 한다. (g_chess의 인덱스와 chessMap의 값은 매핑시켜둠)

   빨간 색일 경우 moveList를 reverse시킨다.

 

* 파란색의 경우 방향을 바꾸고 얻은 위치는 다시 한번 범위를 벗어나는지 체크 해야 한다.

* 매 순간순간 현재 체스의 갯수 합이 4가 넘으면 종료 시켜야 한다. (이 조건을 체크하지 않아 시간이 좀 걸렸다..)

 

 

소스코드(c++)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct chess {
	int x;
	int y;
	int dir;
}typedef chess;

int N, K;
int map[12][12];
vector<int> chessMap[12][12];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<chess> g_chess;

void removeAndMove(int x, int y, int val, int nx, int ny, int color) {
	vector<int>::iterator itr = find(chessMap[y][x].begin(), chessMap[y][x].end(), val);
	vector<int> moveList;
	for (itr; itr != chessMap[y][x].end();) {
		moveList.push_back(*itr);
		itr = chessMap[y][x].erase(itr);
	}

	if (color == 1) {
		reverse(moveList.begin(), moveList.end());
	}

	for (int i = 0; i < moveList.size(); i++) {
		int chessId = moveList[i];
		g_chess[chessId].x = nx;
		g_chess[chessId].y = ny;
		chessMap[ny][nx].push_back(chessId);
	}
}

int calcNewDis(int d) {
	switch (d)
	{
		case 0: return 1;
		case 1: return 0;
		case 2: return 3;
		case 3: return 2;
	}
}

int solution()
{
	int count = 0;
	while (count <= 1000) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (chessMap[i][j].size() >= 4) {
					return count;
				}
			}
		}
		
		for (int i = 0; i < K; i++) {
			chess &curChess = g_chess[i];
			int nx = curChess.x + dx[curChess.dir];
			int ny = curChess.y + dy[curChess.dir];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[ny][nx] == 2) {
				curChess.dir = calcNewDis(curChess.dir);
				nx = curChess.x + dx[curChess.dir];
				ny = curChess.y + dy[curChess.dir];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[ny][nx] == 2) continue;
			}
			
			if (map[ny][nx] == 0) {
				removeAndMove(curChess.x, curChess.y, i, nx, ny, 0);
			}
			else if (map[ny][nx] == 1) {
				removeAndMove(curChess.x, curChess.y, i, nx, ny, 1);
			}
			if (chessMap[ny][nx].size() >= 4) return count + 1;
		}
		count++;
	}
	return -1;
}

int main()
{
	scanf("%d %d",&N, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 0; i < K; i++) {
		int x, y, d;
		scanf("%d %d %d", &y, &x, &d);
		chess tmp = { x - 1, y - 1, d - 1 };
		g_chess.push_back(tmp);
		chessMap[y - 1][x - 1].push_back(i);
	}
	printf("%d\n", solution());
}

 

결과