백준 19237번 : 어른 상어

sol : 72' 55''

• 수행 시간 : 0ms
• 메모리 : 2028KB

Learnings

• 게임 종료 조건을 변수 하나로 가져가자.
  -> O(m)에서 O(1)로 단축.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

#define MAX_N 20
#define EMPTY 0

#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

pair<int, int> markGrid[MAX_N][MAX_N];
int sharkGrid[MAX_N][MAX_N];
const int ds[5][2] = { {0, 0}, { -1, 0 }, {1, 0}, {0, -1}, {0, 1} };

int n, m, k;
int sharkNum;

struct Shark {
	int i;
	int j;
	int dir;
	int prefers[5][5];
	bool removed;

	Shark() : i(-1), j(-1), dir(0), removed(true) {}
};

vector<Shark> sharks;

void DebugMG() {
	cout << endl << "DEBUG MG" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << markGrid[i][j].first << "," << markGrid[i][j].second << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG MG FIN" << endl;
}

void DebugSG() {
	cout << endl << "DEBUG SG" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << sharkGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG SG FIN" << endl;
}

void Init() {
	cin >> n >> m >> k;
	sharks.resize(m + 1);
	sharkNum = m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> sharkGrid[i][j];
			if (sharkGrid[i][j] != EMPTY) {
				sharks[sharkGrid[i][j]].i = i;
				sharks[sharkGrid[i][j]].j = j;
				sharks[sharkGrid[i][j]].removed = false;
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		cin >> sharks[i].dir;
	}

	for (int i = 1; i <= m; i++) {
		for (int d = 1; d <= 4; d++) {
			for (int nd = 1; nd <= 4; nd++) {
				cin >> sharks[i].prefers[d][nd];
			}
		}
	}
}

bool InGrid(int i, int j) {
	return 0 <= i && i < n && 0 <= j && j < n;
}

void InitSharkGrid() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sharkGrid[i][j] = EMPTY;
		}
	}
}

void Mark() {
	for (int s = 1; s <= m; s++) {
		if (sharks[s].removed) continue;

		markGrid[sharks[s].i][sharks[s].j] = make_pair(s, k);
	}
}

void Reduce() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (markGrid[i][j].first > 0) {
				if (markGrid[i][j].second == 1) {
					markGrid[i][j] = make_pair(EMPTY, 0);
				}
				else {
					markGrid[i][j].second--;
				}
			}
		}
	}
}

void Moving(int id, int i, int j, int dir) {
	if (sharkGrid[i][j] != EMPTY) {
		sharks[sharkGrid[i][j]].removed = true;
		sharkNum--;
	}

	sharkGrid[i][j] = id;
	sharks[id].i = i, sharks[id].j = j, sharks[id].dir = dir;
}

void Move() {
	InitSharkGrid();
	for (int s = m; s > 0; s--) {
		if (sharks[s].removed) continue;

		int ci = sharks[s].i, cj = sharks[s].j, cd = sharks[s].dir;
		bool moved = false;
		for (int d = 1; d <= 4; d++) {
			int nd = sharks[s].prefers[cd][d];
			int ni = ci + ds[nd][0];
			int nj = cj + ds[nd][1];

			if (!InGrid(ni, nj)) continue;
			if (markGrid[ni][nj].first == EMPTY) {
				moved = true;
				Moving(s, ni, nj, nd);
				break;
			}
		}
		if (!moved) {
			for (int d = 1; d <= 4; d++) {
				int nd = sharks[s].prefers[cd][d];
				int ni = ci + ds[nd][0];
				int nj = cj + ds[nd][1];

				if (!InGrid(ni, nj)) continue;
				if (markGrid[ni][nj].first == s) {
					Moving(s, ni, nj, nd);
					break;
				}
			}
		}
	}
}

int main() {
	Init();

	Mark();

	int sec = 0;
	while (++sec <= 1000) {
		 Move();
		 if (sharkNum == 1) {
			 cout << sec;
			 return 0;
		 }

		 Reduce();
		 
		 Mark();
	}

	cout << -1;

	return 0;
}