[BOJ] 17837 : 새로운 게임2 - travelbeeee

문제 : https://www.acmicpc.net/problem/17837

---

[ 알고리즘풀이 ]

- 정의

chess[X][Y] : (X, Y) 지점에서의 체스판 상태

horseState[X][Y] : (X, Y) 지점에서의 체스판 위의 말들 상태

horse[X] : X 번 째 말의 현재 위치와 방향

 

1. 각 count 마다 0 ~ K - 1번까지 말들을 순회하며 말들을 move함수를 통해 이동시켜준다.

2. move 함수

- 현재 위치와 다음 위치를 계산한다.

- horseState를 순회하며 현재 위치에서 내가 아래에서부터 몇 번째 말인지 저장한다. ( 내 위의 말들은 같이 이동해야 하므로 )

- 다음 위치가 범위를 벗어났거나, 파란색 칸이면 방향을 바꿔준다.

changeDir[5] = { 0, 1, -1, 1, -1 }

curDir = curDir + changeDir[curDir];

( changeDir 배열을 다음과 같이 선언하면, 현재 방향에서 다음 방향을 쉽게 구할 수 있다. )

- 2번에 의해 방향이 바뀐 경우가 있으므로, 다시 다음 위치를 계산한다.

- 다음 위치가 범위를 벗어났거나, 파란색 칸이면 stop.

- 다음 위치가 흰색 칸이면 내 위의 말들을 다 같이 다음 위치로 이동하고, 그만큼 현재 위치에 pop을 진행.

- 다음 위치가 빨간색 칸이면 내 위의 말들을 다 같이 다음 위치로 거꾸로 이동하고, 그만큼 현재 위치에 pop을 진행.

3. move 함수를 진행할 때마다 게임이 끝났는지 check한다.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int N, K, chess[12][12] = {}, changeDir[5] = { 0, 1, -1, 1, -1 }, dx[5] = { 0, 0, 0, -1, 1 }, dy[5] = { 0, 1, -1, 0, 0 }, a, b, c;
string horseState[12][12]; // 현재 chess판 위의 말 상태저장.
vector<pair<pair<int, int>, int>> horse; // 0 ~ K - 1번 위치저장.


bool checkMap(void) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (horseState[i][j].length() >= 4)
				return true;
	return false;
}

void move(int i) {
	int curX = horse[i].first.first, curY = horse[i].first.second;
	int nextX = curX + dx[horse[i].second], nextY = curY + dy[horse[i].second];
	// j번 째 지점에 존재.
	int j = 0;
	for (j = 0; j < horseState[curX][curY].length(); j++){
		if (horseState[curX][curY][j] == char(i + '0')) {
			break;
		}
	}

	if ((nextX < 0 || N - 1 < nextX || nextY < 0 || N - 1 < nextY) || chess[nextX][nextY] == 2)
		horse[i].second = horse[i].second + changeDir[horse[i].second];

	nextX = curX + dx[horse[i].second], nextY = curY + dy[horse[i].second];

	if ((nextX < 0 || N - 1 < nextX || nextY < 0 || N - 1 < nextY) || chess[nextX][nextY] == 2)
		return;
	else { //흰색 빨간색
		if (chess[nextX][nextY] == 0){
			for (int k = j; k < horseState[curX][curY].length(); k++){
				horseState[nextX][nextY] += horseState[curX][curY][k];
				horse[horseState[curX][curY][k] - '0'].first.first = nextX;
				horse[horseState[curX][curY][k] - '0'].first.second = nextY;
			}
		}
		else {
			for (int k = horseState[curX][curY].length() - 1; k >= j; k--) {
				horseState[nextX][nextY] += horseState[curX][curY][k];
				horse[horseState[curX][curY][k] - '0'].first.first = nextX;
				horse[horseState[curX][curY][k] - '0'].first.second = nextY;
			}
		}
		j = horseState[curX][curY].length() - j;
		for (int k = 0; k < j; k++)
			horseState[curX][curY].pop_back();
	}

	return;
}

void playGame(void) {
	int count = 0;
	if (checkMap()) {
		cout << count;
		return;
	}
	while (count++ <= 1000) {
		for (int i = 0; i < K; i++) {
			move(i);
			if (checkMap()) {
				cout << count;
				return;
			}
		}
	}
	cout << -1;
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> chess[i][j];

	for (int i = 0; i < K; i++) {
		cin >> a >> b >> c;
		a--, b--;
		horseState[a][b] += char(i + '0');
		horse.push_back(make_pair(make_pair(a, b), c));
	}

	playGame();

	return 0;
}

문제를 이해할 때까지 제대로 읽자,,,,,

---