[백준] 주사위 굴리기

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

14499번: 주사위 굴리기

 

주사위 인덱싱을 고려해야하는 문제였다.

 

주사위를 위쪽, 뒤쪽, 오른쪽, 왼쪽, 앞쪽, 아래쪽 순으로 인덱스를 1~6로 할당한다.

인덱스를 맞추기 위해 앞에 0을 추가.

- 기본 주사위 : {0,1,2,3,4,5,6}

 

움직이면 다음과 같다.

동쪽 : {4,2,1,6,5,3}

서쪽 : {3,2,6,1,5,4}

북쪽 : {5,1,3,4,6,2}

남쪽 : {2,6,3,4,1,5} 

 

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int N, K;
int answer;
vector<int> game[13][13];
vector<vector<int>> horse;
int board[13][13];
int dr[4] = { 0,0,-1,1 };
int dc[4] = { 1,-1,0,0 };

bool isFinish() {
	for (int i = 0; i < K; i++) {
		int row = horse[i][0];
		int col = horse[i][1];

		if (game[row][col].size() >= 4) return true;
	}
	return false;
}

bool inRange(int r, int c) {
	return r >= 1 && r <= N && c >= 1 && c <= N;
}

int findPos(int row, int col, int num) {
	vector<int> v = game[row][col];

	for (int i = 0; i < v.size(); i++) {
		if (v[i] == num) {
			return i;
		}
	}
	return -1;
}

int changeDir(int dir) {
	if (dir == 1) return 2;
	else if (dir == 2) return 1;
	else if (dir == 3) return 4;
	else return 3;
}

void moveHorse(int row, int col, int nr, int nc, int dir, int horse_num, int color) {
	int idx = findPos(row, col, horse_num);

	if (color == 0) { //흰색

		//이동한 칸, horse에 업데이트
		int cnt = 0;
		for (int j = idx; j < game[row][col].size(); j++) {
			game[nr][nc].push_back(game[row][col][j]);
			horse[game[row][col][j]][0] = nr;
			horse[game[row][col][j]][1] = nc;
			cnt++;
		}

		//이동하기 전 칸 업데이트
		for (int j = 0; j < cnt; j++) {
			game[row][col].pop_back();
		}
	}
	else if (color == 1) { //빨간색

		//이동한 칸, horse에 업데이트
		int cnt = 0;
		for (int j = game[row][col].size() - 1; j >= idx; j--) {
			game[nr][nc].push_back(game[row][col][j]);
			horse[game[row][col][j]][0] = nr;
			horse[game[row][col][j]][1] = nc;
			cnt++;
		}

		//이동하기 전 칸 업데이트
		for (int j = 0; j < cnt; j++) {
			game[row][col].pop_back();
		}
	}
	else if (color == 2) { //파란색
		dir = changeDir(dir);
		nr = row + dr[dir - 1];
		nc = col + dc[dir - 1];
		horse[horse_num][2] = dir;

		if (inRange(nr, nc) && board[nr][nc] != 2) {
			moveHorse(row, col, nr, nc, dir, horse_num, board[nr][nc]);
		}
	}
}

void  solve() {
	int time = 0;

	while (true){
		if (time > 10000) {
			answer = -1;
			break;
		}
		time++;

		for (int i = 0; i < K; i++) {
			int row = horse[i][0];
			int col = horse[i][1];
			int dir = horse[i][2];

			int nr = row + dr[dir - 1];
			int nc = col + dc[dir - 1];

			if (inRange(nr, nc)) { //체스판을 벗어나지 않는 경우
				moveHorse(row, col, nr, nc, dir, i, board[nr][nc]);
			}
			else { // 체스판을 벗어나는 경우
				moveHorse(row, col, nr, nc, dir, i, 2);
			}

			//확인용
			//for (int i = 0; i < K; i++) {
			//	cout << i << ": " << horse[i][0] << " " << horse[i][1] << " " << horse[i][2] << endl;
			//}
			//cout << endl;
			if (isFinish()) {
				answer = time;
				return;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	//freopen("input.txt", "r", stdin);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < K; i++) {
		int r, c, dir;

		cin >> r >> c >> dir;
		horse.push_back({r,c,dir });
		game[r][c].push_back(i);
	}

	solve();

	cout << answer << endl;
	return 0;
}