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

17837번: 새로운 게임 2

삼성 SW 역량 테스트 기출 문제 수록 문제.

구현 / 시뮬레이션 문제로, 초반에 설계를 잘 하고 들어가면 쉽게 풀 수 있는 문제.

정답률이 46퍼인 만큼, 테스트 케이스만 맞추면 거의 맞출 수 있는 것 같다.

 

문제 풀이

문제의 조건은 다음과 같이 정리할 수 있다.

• N * N 체스판에 말이 K개 존재한다. 말은 초반 입력에는 겹치지 않지만, 겹칠 수 있다.
• 체스판의 각 칸은 흰색(0), 빨간색(1), 파란색(2)일 수 있다.
• 각 말은 1~K번이며 각 말마다 이동방향이 존재한다. (우:1, 좌:2, 상:3, 하:4)

 

각 턴마다 1~K번 말이 이동하는데, 다음과 같은 조건이 붙는다.

• A번 말이 움직일 때, 올려져 있는 말들도 같이 이동한다.
• 이동한 칸에 말이 4개 이상 쌓이면 게임이 종료된다.
• 만일 턴이 1000번째가 넘어가면 게임이 종료된다.

 

말의 이동에 대한 세부 조건은 다음과 같다.

• 말 A(, B, C, ...)가 이동한다고 할 때, 이동하려는 칸이
  • 흰색 : 해당 칸으로 이동하고, 가장 위에 말 A(, B, C, ...)를 올린다.
  • 빨간색 : 해당 칸으로 이동하고, 이동한 말들의 순서를 변경한다. 즉 이동 후에는 (..., C, B, ,)A가 된다.
  • 파란색 & 범위 벗어남 :
    방향을 반대로 하고 이동을 시도한다. 반대로 해도 파란색이거나 범위를 벗어나면 이동하지 않는다.

 

위 조건들을 구현해주면 된다.

 

문제 구현

• 말 구조체 : 번호 / 현재 좌표 / 방향 / 현재 좌표에서 몇 번째인지
• 체스판 정보 : 현재 칸 색깔 / 현재 칸에 몇 개의 말 있는 지
• 우선순위 큐를 이용해 이동시킨다.
  
  • 다음 칸 흰색일 경우 : 이동할 말들과 이동할 말 위에 있는 말들을 큐에 넣고, 우선순위 큐는 idx작은 순서대로 움직이게 구현.
  • 다음 칸 빨간색일 경우 : 이동할 말들과 이동할 말 위에 있는 말들을 큐에 넣고, 우선순위 큐는 idx큰 순서대로 움직이게 구현.
  • 다음 칸 파란색이거나 범위 밖일 경우 : 방향 반대로 하고 색깔 확인
    • 흰색 : 위와 같음.
    • 빨간색 : 위와 같음.
    • 파란색이거나 범위 밖 : 움직이지 않음.

이 때, 각 말의 이동을 한 후에는 체스판 정보도 업데이트 해줘야 한다.

 

문제 코드

 

/*
* 백준 17837번 새로운 게임 2
* https://www.acmicpc.net/problem/문제번호
* - 분류
*/
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Horse {
	int r = 0;
	int c = 0;
	int direction = 0;
	int idxInCurrentBoard = 0;
	int number = 0;
};

struct ChessBoard {
	int color = 0;
	int horseCntInCurrent;
};

int widthHeight, horseCnt;
bool horseOverFour;
int result = -1;
ChessBoard chessBoard[13][13];
vector<Horse> horseVec;
pair<int, int> directions[5] = {
	{-1, -1},
	{0, 1},
	{0, -1},
	{-1, 0},
	{1, 0}
};
int reverseDirections[5] = {-1, 2, 1, 4, 3};

struct compForWhite {
	bool operator()(Horse h1, Horse h2) {
		return h1.idxInCurrentBoard > h2.idxInCurrentBoard;
	}
};

struct compForRed {
	bool operator()(Horse h1, Horse h2) {
		return h1.idxInCurrentBoard < h2.idxInCurrentBoard;
	}
};

void moveForWhite(int idx) {
	priority_queue<Horse, vector<Horse>, compForWhite> pq;
	int curR = horseVec[idx].r;
	int curC = horseVec[idx].c;
	int curIdx = horseVec[idx].idxInCurrentBoard;

	int nxtR = horseVec[idx].r + directions[horseVec[idx].direction].first;
	int nxtC = horseVec[idx].c + directions[horseVec[idx].direction].second;

	for (int i = 0; i < horseVec.size(); i++) {
		if (horseVec[i].r == curR && horseVec[i].c == curC && horseVec[i].idxInCurrentBoard >= curIdx) {
			pq.push(horseVec[i]);
		}
	}

	while (!pq.empty()) {
		Horse curHorse = pq.top();
		pq.pop();

		horseVec[curHorse.number - 1].r = nxtR;
		horseVec[curHorse.number - 1].c = nxtC;
		horseVec[curHorse.number - 1].idxInCurrentBoard = ++chessBoard[nxtR][nxtC].horseCntInCurrent;
		chessBoard[curR][curC].horseCntInCurrent--;
	}

	if (chessBoard[nxtR][nxtC].horseCntInCurrent >= 4) {
		horseOverFour = true;
	}
}

void moveForRed(int idx) {
	priority_queue<Horse, vector<Horse>, compForRed> pq;
	int curR = horseVec[idx].r;
	int curC = horseVec[idx].c;
	int curIdx = horseVec[idx].idxInCurrentBoard;

	int nxtR = horseVec[idx].r + directions[horseVec[idx].direction].first;
	int nxtC = horseVec[idx].c + directions[horseVec[idx].direction].second;

	for (int i = 0; i < horseVec.size(); i++) {
		if (horseVec[i].r == curR && horseVec[i].c == curC && horseVec[i].idxInCurrentBoard >= curIdx) {
			pq.push(horseVec[i]);
		}
	}

	while (!pq.empty()) {
		Horse curHorse = pq.top();
		pq.pop();

		//cout << curHorse.number << " , ";

		horseVec[curHorse.number - 1].r = nxtR;
		horseVec[curHorse.number - 1].c = nxtC;
		horseVec[curHorse.number - 1].idxInCurrentBoard = ++chessBoard[nxtR][nxtC].horseCntInCurrent;
		chessBoard[curR][curC].horseCntInCurrent--;
	}

	if (chessBoard[nxtR][nxtC].horseCntInCurrent >= 4) {
		horseOverFour = true;
	}
}

void go(int idx) {
	if (idx > 1000) return;

	//cout << idx << "\n";
	//for (int i = 1; i <= widthHeight; i++) {
	//	for (int j = 1; j <= widthHeight; j++) {
	//		cout << chessBoard[i][j].horseCntInCurrent << " ";
	//	}
	//	cout << "\n";
	//}

	// 말 이동
	for (int i = 0; i < horseVec.size(); i++) {
		int nxtR = horseVec[i].r + directions[horseVec[i].direction].first;
		int nxtC = horseVec[i].c + directions[horseVec[i].direction].second;
		//cout << i + 1 << "번 말 이동 : " << nxtR << " , " << nxtC << "\n";

		if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight || chessBoard[nxtR][nxtC].color == 2) {
			horseVec[i].direction = reverseDirections[horseVec[i].direction];
			nxtR = horseVec[i].r + directions[horseVec[i].direction].first;
			nxtC = horseVec[i].c + directions[horseVec[i].direction].second;

			if (nxtR < 1 || nxtR > widthHeight || nxtC < 1 || nxtC > widthHeight || chessBoard[nxtR][nxtC].color == 2) continue;
			else if (chessBoard[nxtR][nxtC].color == 0) {
				moveForWhite(i);
			}
			else if (chessBoard[nxtR][nxtC].color == 1) {
				moveForRed(i);
			}

		}
		else if (chessBoard[nxtR][nxtC].color == 0) {
			moveForWhite(i);
		}
		else if (chessBoard[nxtR][nxtC].color == 1) {
			moveForRed(i);
		}
	}

	if (horseOverFour) {
		result = idx;
		return;
	}
	else {
		go(idx + 1);
	}
}

int main() {
	cin >> widthHeight >> horseCnt;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> chessBoard[i][j].color;
		}
	}

	int r, c, dir;
	for (int i = 1; i <= horseCnt; i++) {
		cin >> r >> c >> dir;
		chessBoard[r][c].horseCntInCurrent++;
		horseVec.push_back({ r, c, dir, 1, i });
	}

	go(1);

	cout << result;

	return 0;
}