백준 19237 어른 상어

 

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

19237번: 어른 상어

 

- 맵의 크기는 최대 N^2이고, 총 t초동안 이동가능하므로 O(t * N^2)이므로 시간초과는 나지 않는다.

 

- 가장 먼저, 상어들이 이동하기 위한 좌표를 한 번에 구한다. 한 번에 이동까지 하도록 구현을 하면, 로직이 굉장히 복잡해 질 것이다.(상어들이 한 번에 이동을 하는 것을 가정하기 때문에, 한 마리씩 이동시키는 것은 거의 불가능할 것이다.)

만약 이동 할 상어가 1마리인 경우(즉, 1번상어만 남는 경우) 로직을 종료시킨다.

 

- 다음으로, 상어를 이동시킨다. 여기서 여러 분기로 나눌 수 있는데, 이동하려는 칸이

 

  1. 완전히 빈 칸인 경우, 해당 칸에 상어의 정보(상어의 번호, 상어의 냄새 유통기한(k), 상어 여부(true), 이동 완료 여부(true)를 넣어주기만 하면 된다. 또, 상어가 떠난 자리에는 냄새의 유통기한을 k로 넣어주고, 나중에 한 번에 유통기한이 -1될 때 함께 처리되도록 구현을 한다.

 

  2. 냄새만 존재하는 경우, 기존에 존재하는 정보를 pop_back 해 주고 위 로직대로 새로운 정보를 넣어주면 된다.

위와 마찬가지로 상어가 떠난 자리에는 냄새의 유통기한을 k로 넣어주고, 나중에 한 번에 유통기한이 -1될 때 함께 처리되도록 구현을 한다.

 

  3. 상어가 존재하는 경우, 현재 상어와 비교해서 만약 현재 상어의 번호가 더 크다면 상어를 없애주고, 아닌 경우 기존 상어의 정보를 pop_back 해 주고 새로운 상어의 정보를 넣어준다. 또한 떠난 자리에 냄새를 남겨준다.

 

- 처음 설계에서 고전을 하는 바람에 무려 3시간이 걸리고 말았다. ㅠㅠ 코테가 최신 기출로 갈 수록 어려워지는 느낌이다. 슬슬 자신감이 없어지는데.. 이제까지 풀었던 문제들을 복습하면서 설계하는 것을 다시 한 번 연습을 해야겠다.

#include <iostream>
#include <vector>
using namespace std;
int n, m, k;
vector<pair<pair<int,int>, pair<bool, bool>>> map[20][20]; // 상어의 번호, 냄새 유통기한, 상어의 존재 유무, 이동 여부
int shark_num;
int shark_dir[401];
int shark_priority[401][4][4]; // 각각 상어의 번호, 상어가 해당 방향을 바라볼 때, 상어의 우선 순위
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1 };
/*void debugging() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j].empty()) {
				cout << 0 << 0 << ' ';
			}
			else {
				cout << map[i][j][0].first.first << map[i][j][0].first.second << map[i][j][0].second.first << ' ';
			}
		}
		cout << '\n';
	}
	cout << '\n';
}*/
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int temp;
			cin >> temp;
			if (temp) {
				map[i][j].push_back({ {temp, k}, {true, false} }); 
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		int temp; cin >> temp;
		shark_dir[i] = temp-1;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				cin >> shark_priority[i][j][k];
			}
		}
	}
	int t = 0;
	while (t <= 1000) {
		vector<pair<int, int>> shark_next_area;
		//상어이동
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!map[i][j].empty() && map[i][j][0].second.first == true) {
					// 이동 시작
					int shark_num = map[i][j][0].first.first; int now_shark_dir = shark_dir[shark_num];
					int prior_dir[4]; // 현재 shark의 우선순위를 계산할 배열
					for (int k = 0; k < 4; k++) prior_dir[k] = shark_priority[shark_num][now_shark_dir][k]-1;
					int next_x = -1; int next_y = -1;
					for (int k = 0; k < 4; k++) { // 냄새가 없는 칸 먼저 탐색
						int nx = i + dx[prior_dir[k]]; int ny = j + dy[prior_dir[k]];
						if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if (map[nx][ny].empty()) { // 냄새가 없는 칸이 존재하면, 다음 이동할 칸으로 지정
							next_x = nx; next_y = ny; shark_dir[shark_num] = prior_dir[k];  break;
						}
					}
					if (next_x == -1) { //냄새가 없는 칸이 없다면, 자신의 냄새가 있는 칸을 탐색
						for (int k = 0; k < 4; k++) { // 냄새가 없는 칸 먼저 탐색
							int nx = i + dx[prior_dir[k]]; int ny = j + dy[prior_dir[k]];
							if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny].empty()) continue;
							if (map[nx][ny][0].first.first == shark_num) {
								next_x = nx; next_y = ny;  shark_dir[shark_num] = prior_dir[k]; break;
							}
						}
					}
					shark_next_area.push_back({ next_x, next_y });
				}
			}
		}
		if (shark_next_area.size() == 1) {
			cout << t;
			return 0;
		}
		//이동
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!map[i][j].empty() && map[i][j][0].second.first == true && map[i][j][0].second.second == false) {
					int nx = shark_next_area[0].first; int ny = shark_next_area[0].second;
					shark_next_area.erase(shark_next_area.begin());
					int shark_num = map[i][j][0].first.first;
					if (map[nx][ny].empty()) { //아무것도 없는 경우
						map[nx][ny].push_back({ { shark_num, k },{ true, true } });
						map[i][j].erase(map[i][j].begin());
						map[i][j].push_back({ { shark_num, k },{ false, true } });
					}
					else if(map[nx][ny][0].second.first == false){ // 냄새만 존재하는 경우
						map[nx][ny].erase(map[nx][ny].begin());
						map[nx][ny].push_back({ { shark_num, k },{ true, true } });
						map[i][j].erase(map[i][j].begin());
						map[i][j].push_back({ { shark_num, k },{ false, true } });
					}
					else { //상어가 있는 경우
						if (shark_num > map[nx][ny][0].first.first) { // 이동하려는 곳의 상어 번호가 더 작다면, 현재 상어는 냄새만 남기고 없앤다.
							map[i][j].pop_back();
							map[i][j].push_back({ {shark_num, k }, {false, true} });
						}
						else {
							map[nx][ny].pop_back();
							map[nx][ny].push_back({ {shark_num, k}, {true, true} });
							map[i][j][0].second.first = false;
						}
					}
				}
			}
		} // 냄새의 k값을 1씩 빼 준다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!map[i][j].empty() && map[i][j][0].second.first == false) {
					map[i][j][0].first.second--;
					if (!map[i][j][0].first.second) map[i][j].pop_back();	
				}
				if (!map[i][j].empty() && map[i][j][0].second.first == true) map[i][j][0].second.second = false;
				
			}
		}
		t++;
	}
	cout << -1;
	return 0;
}