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

17837번: 새로운 게임 2

클래스를 하나 만들어

int 형 : 말의 좌표 x, y, 방향 d와

string 형 : 말이 쌓아져 있는 상태 a

의 형태로 벡터에 입력받았다.

 

현재 말이 현재 칸에서 현재 방향으로 이동하려고 할 때 이동하려는 칸이

 

1. 파란색이거나 체스판을 벗어나는 경우

방향을 반대로 바꾼 뒤 그 방향으로 이동할 때

그 칸이 파란색이거나 체스판을 벗어나는 경우는 continue로 넘겨버리고

그 외의 경우는 2, 3번의 경우를 만족하는지 계속 비교하러 간다.

 

2. 하얀색인 경우

방향을 바꾸거나 순서를 뒤집을 필요 없이

바로 이동하려는 칸으로 옮기면 되기 때문에

Reorder 함수만 호출해준다.

 

Reorder 함수는

(1) 이동하려는 말의 윗부분도 위치를 이동시키고

(2) 이동하려는 칸에 말이 있다면 그 위에 쌓는 함수이다.

 

예를 들어 1번 말을 이동시킨다고 할 때

1번 말의 상태 : 1 2 3 (밑→위 순서)

2번 말의 상태 : 2 3

3번 말의 상태 : 3

 

이러면

(1) 1번 말을 옮길 때 1번 말의 윗부분인 2, 3번 말도

자동으로 옮겨져야 하므로

2, 3번 말의 위치도 바꿔야 한다.

 

만약 이동하려는 칸이 비어있지 않고 4번 말이 있다면

4번 말의 상태 : 4 5

5번 말의 상태 : 5

 

그 위에 1번 말을 쌓아야 한다.

4번 말의 상태 : 4 5 1 2 3

5번 말의 상태 : 5 1 2 3

 

그러기 위해선

(2) 4, 5번 말의 상태에 1번 말의 상태를 더한 값을 갱신해주어야 한다.

그리고 갱신할 때마다 쌓여있는 말이 4개 이상이면

이때의 턴을 출력한 뒤 종료한다.

 

3. 빨간색인 경우

임시 string을 만들어

현재 말의 형태를 뒤집은 값을 저장한 후

맨 밑에 있는 말부터 다시 저장한다.

 

예를 들어 1번 말을 이동하려고 할 때

1번 말의 상태 : 1 2 3 4 (밑→위 순서)

2번 말의 상태 : 2 3 4

3번 말의 상태 : 3 4

4번 말의 상태 : 4

 

뒤집음 : 4 3 2 1

 

1번 말의 상태 : 1

2번 말의 상태 : 2 1

3번 말의 상태 : 3 2 1

4번 말의 상태 : 4 3 2 1

 

이렇게 뒤집은 다음

원래 옮기려고 했던 1번 말부터 옮기는 것이 아니라

자기 자신 위에 가장 많은 말이 쌓여 있는 4번 말을 옮겨야 한다.

 

그럼 Reorder 함수에서 자동으로

4번 말의 상태에 있는 3, 2, 1번 말들도 옮겨준다.

 

이 과정을 반복하면서 턴이 1000회를 넘으면 -1을 출력한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int N, K, x, y, d, res;
int board[13][13], dx[4] = { 0, 0, -1, 1 }, dy[4] = { 1, -1, 0, 0 }, dd[4] = { 1, 0, 3, 2 };
class Horse {
public:
	int x, y, d;
	string a;
	Horse(int x, int y, int d, string a) {
		this->x = x;
		this->y = y;
		this->d = d;
		this->a = a;
	}
};

vector <Horse> v;

void Reorder(int k) {
	for (int i = 0; i < K; i++) {
		if (i == k) continue;
		if (x == v[i].x && y == v[i].y) { // 이동하려는 칸의 말 위에 올려놓음
			v[i].a += v[k].a;
			if (v[i].a.size() >= 4) { // 말이 4개 이상 쌓일 때 게임 종료
				cout << res;
				exit(0);
			}
		}
		else if (v[k].x == v[i].x && v[k].y == v[i].y) { // 이동하기 전 칸의  말 개수 재조정
			if(v[k].a.size() < v[i].a.size()) v[i].a.resize(v[i].a.size() - v[k].a.size()); // 이동하려는 말의 밑 부분만 남게 함
			else v[i].x = x, v[i].y = y; // 이동하려는 말의 윗 부분도 위치가 옮겨짐
		}
	}
	v[k].x = x, v[k].y = y;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> board[i][j];
	for (int i = 0; i < K; i++) {
		cin >> x >> y >> d;
		v.push_back(Horse(x - 1, y - 1, d - 1, to_string(i)));
	}
    
	while (1) {
		if (res == 1000) break;
		res++;
		for (int k = 0; k < K; k++) {
			x = v[k].x + dx[v[k].d], y = v[k].y + dy[v[k].d]; // 이동하려는 칸이

			if (x < 0 || x >= N || y < 0 || y >= N || board[x][y] == 2) { // 파란색이거나 체스판을 벗어나는 경우
				v[k].d = dd[v[k].d], x = v[k].x + dx[v[k].d], y = v[k].y + dy[v[k].d]; // 방향을 바꾼 뒤 다시 이동하려는 칸이
				if (x < 0 || x >= N || y < 0 || y >= N || board[x][y] == 2) continue; // 체스판을 벗어나거나 파란색인 경우 가만히 있는다
			}

			if (board[x][y] == 1) { // 빨간색인 경우엔 이동하려는 말들의 순서를 반대로 바꾼다
				string tmp = v[k].a;
				reverse(tmp.begin(), tmp.end());
				for (int i = 0; i < tmp.size(); i++) {
					for (int j = 0; j < K; j++) {
						if (v[k].x == v[j].x && v[k].y == v[j].y && j == tmp[i] - '0') {
							v[j].a = tmp.substr(i, tmp.size() - i);
							break;
						}
					}
				}
				Reorder(tmp[0] - '0');
			}

			else Reorder(k); //하얀색인 경우엔 그냥 이동한다
		}
	}
	if (res == 1000) cout << -1;
	else cout << res;
	return 0;
}