[삼성코테기출문제] 새로운 게임 2

새로운 게임2

삼성 문제는 진짜… 너무 어렵다. 아직도 3시간안에 2문제를 풀 자신이 없다. 문제 해석이 조금이라도 벗어나버리면 그때까지 풀었던 코드들은 거의 다 날려야한다. 기출문제를 풀어보면 SWEA에서 풀었던 모의역량테스트는 쉬운편이다…

이 문제는 사실 19년 하반기 기출문제인데 응시했었다. 못풀었다. 풀수있을 것 같았는데 못풀었었다. 다른 한 문제는 손도 못댔고…
이번에 다시 풀어보니 문제 해석도 잘못했던 것 같다.
문제를 풀 때 의역해서 문제를 풀지말고 딱 시키는대로만 풀자!!!

문제

문제 풀이

1. 우선 모든 맵에 대하여 체스 말의 정보 모두가 입력되어야 하므로 deque를 2차원 배열로 만들어준다.
2. 모든 말의 정보를 piece에 저장하고 deq에 현재 정보를 입력한다.
3. 최대 1000턴 동안 piece에 저장된 체스 말들을 이동 시킨다.
4. 각 체스 말의 현재 위치에서 다음 위치로 이동시킨다. 다음 위치가
   1. 흰 색 이라면 현재 말을 다음 위치에 push back해준다. 현재 말 위에 다른 말들이 있다면 현재 말 부터 마지막 말까지 순서로 다음 위치에 옮겨준다
   2. 빨간 색 이라면 현재 말을 다음 위치에 push back해준다. 현재 말 위에 다른 말들이 있다면 마지막 말 부터 현재 말까지 순서로 다음 위치에 옮겨준다 (데크를 쓰는 이유)
5. 만약 다음 위치가 파란색이나 범위를 벗어난다면 현재 말의 방향을 반대로 전환하고 한 칸 이동시켜준다. 다시 한 칸 움직이는 것이므로 이 경우 위의 1, 2 번 경우를 다시 확인해준다. 만약 다음 위치 역시 파란색이거나 범위를 벗어난다면 이동하지 않고 그대로 있는다.
6. 위 과정을 반복하면서 한 위치에 4개 이상의 말이 쌓이는 경우 그 때의 turn수를 반환하고, 1000턴 후에도 4개 이상의 말이 쌓이는 경우가 없을 때에는 -1을 반환한다.

소스 코드

#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <algorithm>
#define PII pair<int,int>

using namespace std;

const int MAX = 13;

int N, K;
int Map[MAX][MAX];		// 1:빨간색(모든 순서 바꿈), 2:파란색(방향 전환 후 한 칸)
struct Pos { int y, x, dir; };
Pos piece[MAX];
deque<int> deq[MAX][MAX];	// 해당 좌표의 체스 말 순서

int dy[] = { 0,0,0,-1,1 };
int dx[] = { 0,1,-1,0,0 };


bool isRanged(int y, int x) { return y > 0 && x > 0 && y <= N && x <= N; }
int solution() {
	int turn = 1;

	while (turn <= 1000) {
		for (int i = 1; i <= K; i++) {
			int curx = piece[i].x, cury = piece[i].y;
			int curdir = piece[i].dir;

			int ny = cury + dy[curdir], nx = curx + dx[curdir];

			if (!isRanged(ny, nx) || Map[ny][nx] == 2) {
				int d = piece[i].dir;
				piece[i].dir += d % 2 == 0 ? -1 : 1;
				curdir = piece[i].dir;
				ny = cury + dy[curdir], nx = curx + dx[curdir];
				if (isRanged(ny, nx) && Map[ny][nx] != 2) {
					if (Map[ny][nx] == 0) {
						deque<int> tmp;
						while (1) {
							int a = deq[cury][curx].back();
							deq[cury][curx].pop_back();
							piece[a].y = ny;
							piece[a].x = nx;
							tmp.push_back(a);
							if (i == a)break;
						}
						while (!tmp.empty()) {
							int a = tmp.back();
							tmp.pop_back();
							deq[ny][nx].push_back(a);
							if (deq[ny][nx].size() >= 4)return turn;
						}
					}
					else if (Map[ny][nx] == 1) {
						while (1) {
							int a = deq[cury][curx].back();
							deq[cury][curx].pop_back();
							piece[a].y = ny;
							piece[a].x = nx;
							deq[ny][nx].push_back(a);
							if (deq[ny][nx].size() >= 4)return turn;
							if (i == a)break;
						}
					}
				}
			}
			else {
				if (Map[ny][nx] == 0) {
					deque<int> tmp;
					while (1) {
						int a = deq[cury][curx].back();
						deq[cury][curx].pop_back();
						piece[a].y = ny;
						piece[a].x = nx;
						tmp.push_back(a);
						if (i == a)break;
					}
					while (!tmp.empty()) {
						int a = tmp.back();
						tmp.pop_back();
						deq[ny][nx].push_back(a);
						if (deq[ny][nx].size() >= 4)return turn;
					}

				}
				else if (Map[ny][nx] == 1) {
					while (1) {
						int a = deq[cury][curx].back();
						deq[cury][curx].pop_back();
						piece[a].y = ny;
						piece[a].x = nx;
						deq[ny][nx].push_back(a);
						if (deq[ny][nx].size() >= 4)return turn;
						if (i == a)break;
					}
				}
			}
		}
		turn++;
	}

	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("27.in", "r", stdin);

	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int a; cin >> a;
			Map[i][j] = a;
		}
	}
	for (int i = 1; i <= K; i++) {
		int y, x, dir;
		cin >> y >> x >> dir;
		piece[i] = { y,x,dir };
		deq[y][x].push_back(i);
	}
	cout << solution() << endl;

	return 0;
}