[백준]19237 어른 상어 C++(실패)

55분 + 오류수정 ∞

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

19237번: 어른 상어

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

---

#include<iostream>
#include<vector>
#include<string>
#include<numeric>
using namespace std;

int main() {
	//위,아래,왼쪽,오른쪽
	int xDir[] = {0,0,0,-1,1};
	int yDir[] = {0,-1,1,0,0};

	int answer = 0;
 	int N, M, k;

	cin >> N >> M >> k;

	//shark number
	vector<vector<int>> area(N, vector<int>(N, 0));
	//first : shark number, second : smell count
	vector<vector<pair<int, int>>> smell(N,vector<pair<int,int>>(N,make_pair(0,0))); 
	//index : shark number, current direction
	vector<vector<vector<int>>> prior(M+1,vector<vector<int>>(5,vector<int>(4,0)));
	vector<int> dir(M + 1, 0);
	vector<int> surv(M + 1, 1);
	vector<pair<int, int>> loc(M + 1, make_pair(-1, -1)); //shark location
	

	for(int i=0; i<N; i++) 
		for (int j = 0; j < N; j++) {
			cin >> area[i][j];
			if (area[i][j] != 0) {
				loc[area[i][j]] = make_pair(i, j);
				smell[i][j].first = area[i][j], smell[i][j].second = k;
			}
		}
	for (int i = 1; i <= M; i++) cin >> dir[i];

	//std::cout << prior[0].size() << endl;
	for (int n = 1; n <= M; n++)
		for (int i = 1; i <= 4; i++)
			for (int j = 0; j < 4; j++) {
				cin >> prior[n][i][j];
			}
	
	while (answer < 1000) {
		if (accumulate(surv.begin(), surv.end(), 0) == 2) break;
		answer++;
		//cout << "===============" << answer << "===============" << endl;

		vector<vector<pair<int, int>>> nsmell = smell;
		vector<pair<int,int>> tmp;

		//smell down
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++) {
				if (nsmell[i][j].first != 0) {
					nsmell[i][j].second--;
					if (nsmell[i][j].second == 0)
						tmp.push_back(make_pair(i, j));
				}
			}

		//shark move
		for (int shark = M; shark > 0; shark--) {
			if (!surv[shark]) continue;

			pair<int, int> crnloc = make_pair(loc[shark].first, loc[shark].second);

			//cond1) no smell 
			for (int a = 0; a < 4; a++) {

				int ndir = prior[shark][dir[shark]][a]; //next direction
				int dy = loc[shark].first + yDir[ndir], dx = loc[shark].second + xDir[ndir];

				if (dy >= N || dy < 0 || dx >= N || dx < 0) continue;

				if (nsmell[dy][dx].first == 0) {
					//std::cout << shark << " is moving " << dy << "," << dx << endl;
					loc[shark].first = dy, loc[shark].second = dx;
					dir[shark] = ndir;
					nsmell[dy][dx].first = shark, nsmell[dy][dx].second = k;
					area[crnloc.first][crnloc.second] = 0, area[dy][dx] = shark;
					break;
				}
				//eating
				else if (nsmell[dy][dx].second == k && smell[dy][dx].second == 0) {
					//std::cout << shark << " is eating " << dy << "," << dx << endl;
					surv[nsmell[dy][dx].first] = 0;
					loc[shark].first == dy, loc[shark].second = dx;
					dir[shark] = ndir;
					nsmell[dy][dx].first = shark, nsmell[dy][dx].second = k;
					area[crnloc.first][crnloc.second] = 0, area[dy][dx] = shark;
					break;

				}
				else continue;
			}

			//cond2) my smell 
			if (crnloc == loc[shark]) {

				for (int a = 0; a < 4; a++) {
					int ndir = prior[shark][dir[shark]][a]; //next direction
					int dy = loc[shark].first + yDir[ndir], dx = loc[shark].second + xDir[ndir];

					if (dy >= N || dy < 0 || dx >= N || dx < 0) continue;

					if (nsmell[dy][dx].first == shark) {
						//std::cout << shark << "'s smell" << endl;
						loc[shark].first = dy, loc[shark].second = dx;
						dir[shark] = ndir;
						nsmell[dy][dx].first = shark, nsmell[dy][dx].second = k;
						area[crnloc.first][crnloc.second] = 0, area[dy][dx] = shark;
						break;
					}
				}
			}
		}
		smell = nsmell;
		for (int t = 0; t < tmp.size(); t++) {
			if(smell[tmp[t].first][tmp[t].second].second != k)
				smell[tmp[t].first][tmp[t].second].first = 0;
		}
		/*
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				std::cout << area[n][m]<<" : ("<<smell[n][m].first << "," << smell[n][m].second << ")  ";
			}std::cout << endl;
		}*/
	}
	cout << (answer >= 1000 ? -1 : answer) << endl;

}

 

 

잡아먹는 것은 번호가 작을수록 우위이기 때문에 번호가 큰 상어부터 움직여 아직 향기가 k인 상어는 무시하고 그 자리르 차지하도록 했다. 그래서 난 예외처리로 nsmell 선언이 필요해져 굉장히 비효율적이다..

테스트케이스 4개와 질문의 올라온 반례를 모두 통과하는데도 정답이 틀렸다..!