백준 17837 (새로운 게임 2)

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

17837번: 새로운 게임 2

해당 문제는 N * N 크기의 격자판이 주어지며 격자판에서 움직일 수 있는 말 M개가 주어져 M 개의 말이 이동하여 특정한 위치에 4개 이상 겹치게 둘 경우 현재 진행횟수를 출력하면 되는 문제이다. 추가로 각 말의 위치 정보와 이동할 수 있는 방향이 주어진다. 

게임의 룰은 다음과 같다.

말이 이동중 현재 말 위에 다른 말이 올라가 있다면 위에 있는 모든 말들도 같이 움직인다.

1. 만약 말이 이동한 위치의 격자판 값이 0이라면 이동할 위치에 현재 말 부터 그 위에있는 모든 말들을 격자판 위에 쌓아 올린다.

2. 만약 격자판 값이 1이라면 현재 말 부터 그위에 있는 모든 말들을 옮기 되 가장 위에 있는 말 부터 옮기기 시작한다.

3. 만약 격자판 값이 2라면 현재 말의 위치는 유지하며 방향만 바꾸어 다시 진행한다. 

4. 말의 이동 위치가 격자판을 벗어날 경우 3의 경우와 동일하게 처리한다.

 

풀이 

해당 문제는 크게 3가지 경우가 존재한다고 볼 수 있다. 이동한 위치가 0일경우, 1일경우, 2일경우 or 벗어날경우 따라서 각 경우에 맞는 동작을 수행하는 함수를 3가지 만들어 문제를 해결할 것이다. 

이때 격자판의 정보를 담을 map 배열과 말들이 겹쳐있는 경우를 Cnt 해줄 visit 배열을 운용한다. 또한 각 말들의 현재 좌표와 방향을 담을 Node 구조체 배열도 운용할 것이다.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
struct Node{
	int num;
	int y, x;
	int dir;
};
int checkY[4] = { 0, 0, -1, 1 };
int checkX[4] = { 1, -1, 0, 0 };

// 각 말의 정보
Node nodeList[15];
// 말들이 겹쳐있는 경우를 담을 격자판
vector<int> visit[12][12];
// 실제 격자판
int map[12][12];
int n, k;

int getDir(int dir){
	if (dir == 0) return 1;
	else if (dir == 1) return 0;
	else if (dir == 2) return 3;
	else return 2;
}

// 이동한 격자판이 0일 경우
void moveW(int target){
	Node now = nodeList[target];
	vector<int> vect = visit[now.y][now.x];
	int mL = vect.size();
	int y = now.y;
	int x = now.x;
	int s = 0;
	int delIdx;

	int dy = now.y + checkY[now.dir];
	int dx = now.x + checkX[now.dir];

	// 현재 선택된 말이 몇번째 위치에 올라가 있는지 탐색
	for (int i = 0; i < mL; ++i){
		if (vect[i] == now.num){
			s = i;
			break;
		}
	}
	// 현재 선택된 말의 위치부터 차례대로 이동할 위치에 Push
	for (int i = s; i < mL; ++i){
		visit[dy][dx].push_back(vect[i]);
		nodeList[vect[i]].y = dy;
		nodeList[vect[i]].x = dx;
	}
	visit[y][x].erase(visit[y][x].begin() + s, visit[y][x].end());
}

// 이동한 격자판이 1일경우
void moveR(int target){
	Node now = nodeList[target];
	vector<int> vect = visit[now.y][now.x];
	int mL = vect.size();
	int y = now.y;
	int x = now.x;
	int delIdx;

	int dy = now.y + checkY[now.dir];
	int dx = now.x + checkX[now.dir];

	// 가장 위에 있는 말 부터 선택된 말까지 차례대로 Push
	for (int i = mL - 1; i >= 0; --i){
		visit[dy][dx].push_back(vect[i]);
		nodeList[vect[i]].y = dy;
		nodeList[vect[i]].x = dx;
		if (vect[i] == now.num) {
			delIdx = i;
			break;
		}
	}
	visit[y][x].erase(visit[y][x].begin() + delIdx, visit[y][x].end());
}

// 이동한 격자판이 2일경우 
void moveB(int target){
	nodeList[target].dir = getDir(nodeList[target].dir);
	Node now = nodeList[target];
	int dy = now.y + checkY[now.dir];
	int dx = now.x + checkX[now.dir];

	if (dy < 0 || dx < 0 || dy >= n || dx >= n || map[dy][dx] == 2) return;

	else{
		if (map[dy][dx] == 0) moveW(target);
		else if (map[dy][dx] == 1) moveR(target);
	}

}

bool checkList(){
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (visit[i][j].size() >= 4) return true;
		}
	}
	return false;
}

int getData(){
	int cnt = 0;
	while (cnt <= 1000){
		++cnt;
		if (cnt == 2){
			int f = 1;
		}
		for (int i = 1; i <= k; ++i){
			Node now = nodeList[i];
			int dy = now.y + checkY[now.dir];
			int dx = now.x + checkX[now.dir];
			if (dy < 0 || dx < 0 || dy >= n || dx >= n) moveB(now.num);
			else if (map[dy][dx] == 2) moveB(now.num);
			else if (map[dy][dx] == 1) moveR(now.num);
			else if (map[dy][dx] == 0) moveW(now.num);
			if (checkList() == true) return cnt;
		}
	}
	return -1;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> k;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> map[i][j];
		}
	}
    
	for (int i = 0; i < k; ++i){
		int y, x, dir;
		cin >> y >> x >> dir;
		--y;
		--x;
		--dir;
		nodeList[i + 1] = { i + 1, y, x, dir };
		visit[y][x].push_back(i + 1);
	}

	cout << getData() << endl;
}