백준 - 어른 상어 (19237 번)

백준 - 어른 상어 (19237 번)

정답율이나 티어는 백준 - 청소년 상어 (19236 번)보다 어렵다고 되어 있는데, 훨씬 쉽게 풀었다.

설명이 깔끔해서 그런지 읽는데도 쉬웠고, 구현하는데도 30분안에 구현한 것 같다.

코드는 아래와 같고, 주석을 달아놔서 설명은 따로 필요 없을 것 같다.

#include <iostream>
#include <cstdio>

using namespace std;

typedef struct __perfume_info {
	int shark_idx;
	int time;
} perfume_info;

typedef struct __shark_info {
	int row;
	int col;
	int nrow;
	int ncol;
	int dir;
	int alive;
	int priority_info[4][4];
} shark_info;

int n, m, k;
int map[32][32];
shark_info sharks[512];
perfume_info perfume_map[32][32];

// 상 하 좌 우
int rowDir[4] = { -1, 1, 0, 0 };
int colDir[4] = { 0, 0, -1, 1 };

void dec_perfume(int time)
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (perfume_map[i][j].time == 0)
				continue;
			perfume_map[i][j].time--;
			if (perfume_map[i][j].time == 0)
				perfume_map[i][j].shark_idx = 0;
		}
	}
}

void make_perfume(int time)
{
	for (int i = 1; i <= m; i++) {
		// 쫓겨난 상어는 냄새를 남기지 않음
		if (!sharks[i].alive)
			continue;
		perfume_info perfume = { i, k };
		perfume_map[sharks[i].row][sharks[i].col] = perfume;
	}
}

void move_shark()
{
	int nrow, ncol;
	for (int s = m; s >= 1; s--) {
		if (!sharks[s].alive)
			continue;

		int row = sharks[s].row;
		int col = sharks[s].col;
		int dir = sharks[s].dir;

		int prior_dir[4];
		for (int i = 0; i < 4; i++) 
			prior_dir[i] = sharks[s].priority_info[dir][i];

		// 먼저 인접한 칸 중 빈 칸을 찾아봄
		bool get_clear_empty = false;
		for (int i = 0; i < 4; i++) {
			nrow = row + rowDir[prior_dir[i]];
			ncol = col + colDir[prior_dir[i]];
			if (nrow < 0 || ncol < 0 || nrow > n - 1 || ncol > n - 1)
				continue;
			if (perfume_map[nrow][ncol].time != 0)
				continue;
			get_clear_empty = true;
			dir = i;
			break;
		}
		// 빈 칸을 얻음
		if (get_clear_empty) {
			sharks[s].nrow = nrow;
			sharks[s].ncol = ncol;
			sharks[s].dir = prior_dir[dir];
			continue;
		}

		// 빈 칸이 없을 시 자기 냄새 칸 찾아봐야 함
		bool get_my_perfume = false;
		for (int i = 0; i < 4; i++) {
			nrow = row + rowDir[prior_dir[i]];
			ncol = col + colDir[prior_dir[i]];
			if (nrow < 0 || ncol < 0 || nrow > n - 1 || ncol > n - 1)
				continue;
			if (perfume_map[nrow][ncol].shark_idx != s)
				continue;
			get_my_perfume = true;
			dir = i;
			break;
		}
		// 자기 냄새 칸을 찾음
		if (get_my_perfume) {
			sharks[s].nrow = nrow;
			sharks[s].ncol = ncol;
			sharks[s].dir = prior_dir[dir];
		}
	}

	// map에 상어 정보를 업데이트 (m에서 1 순서로 업데이트 시 작은 것이 항상 map에 남아있을 수 있음)
	for (int s = m; s >= 1; s--) {
		if (!sharks[s].alive)
			continue;
		map[sharks[s].row][sharks[s].col] = 0;
		if (map[sharks[s].nrow][sharks[s].ncol]) 
			sharks[map[sharks[s].nrow][sharks[s].ncol]].alive = false;
		map[sharks[s].nrow][sharks[s].ncol] = s;
		sharks[s].row = sharks[s].nrow;
		sharks[s].col = sharks[s].ncol;
	}

}
void solve(int time)
{
	// 1. 전체에서 냄새를 1씩 감소
	dec_perfume(time);

	// 2. 현재 상어 위치에 냄새를 k만큼 남김
	make_perfume(time);
	
	// 3. 상어 이동
	move_shark();
}

const inline bool is_fin()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0 || map[i][j] == 1)
				continue;
			return false;
		}
	}
	return true;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				sharks[map[i][j]].row = i;
				sharks[map[i][j]].col = j;
				sharks[map[i][j]].nrow = i;
				sharks[map[i][j]].ncol = j;
			}
		}
		
	for (int i = 1; i <= m; i++) {
		cin >> sharks[i].dir;
		sharks[i].dir--;
		sharks[i].alive = true;
	}


	
	for (int s = 1; s <= m; s++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cin >> sharks[s].priority_info[i][j];
				sharks[s].priority_info[i][j]--;
			}
		}
	}
		
	int time = 0;
	while (1) {
		solve(time);

		time++;
		if (time > 1000)
			break;
		if (is_fin())
			break;
	}

	if (time > 1000)
		time = -1;

	cout << time << "\n";
	
	return 0;
}