[삼성역량테스트] 17837 새로운 게임 2

풀이일시 : 2021-03-19

 

문제 : 

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 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번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

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

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

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

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

 

 

입력 :

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

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

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

 

 

 

출력 :

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

 

 

 

제한 : 

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

 

 

풀이 및 코드 : 

 

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

struct mal {
	int rr;
	int cc;
};

vector <pair<int, int>> v[13][13]; //말 번호와 방향이 들어갈것
mal loc[13];
int arr[13][13] = { 0, }; //배열
int N, K;

//방향 : 1-우 2-좌 3-상 4-하

int dc[] = { 0,1,-1,0,0 };
int dr[] = { 0,0,0,-1,1 };

int solution(){
	int cnt = 1;
	int dir = 0;
	int era;
	while (cnt <= 1000) {
		for (int i = 1; i <= K; i++) { //말의 갯수만큼 계속 반복
			//말 i의 위치는?
			int r = loc[i].rr;
			int c = loc[i].cc;
			//말 i의 방향은?
			for (int n = 0; n < v[r][c].size(); n++) {
				int num = v[r][c][n].first;
				if (num == i) {
					dir = v[r][c][n].second;
					era = n;
					break;
				}
			}
			//새롭게 갈 방향을 제시한다.
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			//움직인다면 범위를 벗어나는지 확인한다
			int color = 0;
			if (nr < 1 || nr >= N+1 || nc < 1 || nc >= N+1) color = 2; //벗어났다면 파란색
			//범위를 벗어난 것이 아니라면 갈 곳의 색깔을 확인한다

			if (arr[nr][nc] == 0&&color!=2) { //흰색
				//그 칸으로 이동한다. 
				//이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
				for (int a = era; a < v[r][c].size(); a++) {
					v[nr][nc].push_back({ v[r][c][a].first,v[r][c][a].second });
					loc[v[r][c][a].first].rr = nr;
					loc[v[r][c][a].first].cc = nc;
				}
				if (v[nr][nc].size() >= 4) return cnt;
				v[r][c].erase(v[r][c].begin()+era,v[r][c].end()); //지우기
			}
			else if (arr[nr][nc] == 1&&color!=2) { //빨간색
				for (int a = v[r][c].size() - 1; a >= era; a--) {
					v[nr][nc].push_back({ v[r][c][a].first,v[r][c][a].second }); //거꾸로놓자
					loc[v[r][c][a].first].rr = nr;
					loc[v[r][c][a].first].cc = nc;
				}
				if (v[nr][nc].size() >= 4) return cnt;
				v[r][c].erase(v[r][c].begin() + era, v[r][c].end()); //지우기
			}
			else if (arr[nr][nc] == 2||color==2) { //파란색
				int bluenr = r - dr[dir];
				int bluenc = c - dc[dir];
				//일단 말의 방향을 바꾼다
				switch (v[r][c][era].second) {
				case(1):v[r][c][era].second = 2; break;
				case(2):v[r][c][era].second = 1; break;
				case(3):v[r][c][era].second = 4; break;
				case(4):v[r][c][era].second = 3; break;
				}
				if (bluenr < 1 || bluenr >= N+1 || bluenc < 1 || bluenc >= N+1) continue;
				if (arr[bluenr][bluenc] == 2) continue;//방향바꾼쪽도 파란색이면
				else if(arr[bluenr][bluenc]==0){ // 방향 바꾼쪽이 흰색이면
					for (int a = era; a < v[r][c].size(); a++) {
						v[bluenr][bluenc].push_back({ v[r][c][a].first,v[r][c][a].second }); //그대로 이동
						loc[v[r][c][a].first].rr = bluenr;
						loc[v[r][c][a].first].cc = bluenc;
					}
					if (v[bluenr][bluenc].size() >= 4) return cnt;
					v[r][c].erase(v[r][c].begin() + era, v[r][c].end()); //지운다.
				}
				else if (arr[bluenr][bluenc] == 1) { //빨간색일때
					for (int a = v[r][c].size() - 1; a >= era; a--) {
						v[bluenr][bluenc].push_back({ v[r][c][a].first,v[r][c][a].second }); //거꾸로놓자
						loc[v[r][c][a].first].rr = bluenr;
						loc[v[r][c][a].first].cc = bluenc;
					}
					if (v[bluenr][bluenc].size() >= 4) return cnt;
					v[r][c].erase(v[r][c].begin() + era, v[r][c].end()); //지운다.
				}
			}
		}
		cnt++;
	}
	return -1;
}

int main() {
	cin >> N >> K;
	int color;
	int r, c, d;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> color;
			arr[i][j] = color;
		}
	}
	for (int i = 1; i <= K; i++) {
		cin >> r >> c >> d;
		v[r][c].push_back({ i,d });
		loc[i].rr = r;
		loc[i].cc = c;
	}
	cout << solution() << '\n';

	return 0;
}

 

 

참고자료 : vector

dbstndi6316.tistory.com/25

[개념정리] vector container

참고자료 : deque

dbstndi6316.tistory.com/30

[개념정리] deque container