[시뮬레이션] 백준 19237 어른 상어 C++

※ 문제

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

19237번: 어른 상어

 

※ 풀이

#include<bits/stdc++.h>

using namespace std;

struct Shark {
	int num, x, y, curr, dir[5][5]; // 상어 번호, 위치, 현재 방향, 우선순위 방향
};

struct State {
	int here, num, time; // 상어 번호, 냄새 남긴 상어 번호, 냄새 남은 시간
};

int n, m, k;
int dx[5] = { 0,0,0,-1,1 };
int dy[5] = { 0,-1,1,0,0 };
State board[22][22]; // 상어 번호, 냄새, 시간 기록
Shark sharks[401];

void move(int idx) {
	Shark now = sharks[idx];

	// 원래 있던 칸에 상어 없음 표시
	board[now.y][now.x].here = 0;

	// 냄새 없는 칸으로 이동
	for (int j = 1; j <= 4; j++) {
		int newX = now.x + dx[now.dir[now.curr][j]];
		int newY = now.y + dy[now.dir[now.curr][j]];
		
		if ((newX == 0) || (newY == 0) || (newX > n) || (newY > n)) continue;
		if (board[newY][newX].num == 0) { // 냄새 없을 때
			now.x = newX;
			now.y = newY;
			now.curr = now.dir[now.curr][j];
			sharks[idx] = now;
			return;
		}
	}

	// 자신의 냄새 있는 칸으로 이동
	for (int j = 1; j <= 4; j++) {
		int newX = now.x + dx[now.dir[now.curr][j]];
		int newY = now.y + dy[now.dir[now.curr][j]];
		
		if ((newX == 0) || (newY == 0) || (newX > n) || (newY > n)) continue;
		if (board[newY][newX].num == now.num) { // 자신의 냄새 있을 때
			now.x = newX;
			now.y = newY;
			now.curr = now.dir[now.curr][j];
			sharks[idx] = now;
			return;
		}
	}
}

int check(int idx, int nmg) {
	Shark later = sharks[idx];

	// 큰 상어 번호 격자판 나가게
	if ((board[later.y][later.x].here != 0) && (board[later.y][later.x].here < later.num)) {
		sharks[idx].num = -1;
		nmg--;
	}
	else {
		board[later.y][later.x].here = later.num;
		board[later.y][later.x].num = later.num;
		board[later.y][later.x].time = k;
	}
	return nmg;
}

int start() {
	int nmg = m;
	int runTime = 0;
	while (true) {
		// 모든 상어 이동
		for (int i = 1; i <= m; i++) { // 상어 번호
			if (sharks[i].num == -1) continue; // 격자판 나간 상어 패스
			move(i);
		}

		// 모든 상어 이동 후 격자판 업데이트(작은 번호부터 확인)
		for (int i = 1; i <= m; i++) {
			if (sharks[i].num == -1) continue; // 격자판 나간 상어 패스
			nmg = check(i, nmg);
		}

		// 냄새 시간 흐르게
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (board[i][j].here) continue;
				if (board[i][j].time) board[i][j].time--;
				if (board[i][j].time == 0) board[i][j].num = 0;
			}
		}

		runTime++;

		if (nmg == 1) return runTime;
		if (runTime >= 1000) return -1;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> k;

	int temp;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> temp;
			if (temp) {
				sharks[temp] = { temp,j,i,0,{0,} };
				board[i][j].here = temp;
				board[i][j].num = temp;
				board[i][j].time = k;
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		cin >> temp;
		sharks[i].curr = temp; // 현재 방향
	}

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= 4; j++) { // 해당 방향일 때
			for (int k = 1; k <= 4; k++) { // 우선순위
				cin >> temp;
				sharks[i].dir[j][k] = temp;
			}
		}
	}

	cout << start();
}