[C++] 백준 19237번 - 어른 상어 (구현, 삼성 코테 기출)

문제 링크 : www.acmicpc.net/problem/19237

19237번: 어른 상어

 

문제

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

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

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

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

 

 

 

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 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을 출력한다.

 

 

 

 

 

 

 

접근 방법

 

1단계 : 4방향 검사

현재 상어를 방향을 기준으로 우선위에 따라 돌아가면서 다음 칸을 검사한다.

돌면서 내 냄새와 같은 칸이 나오면 그 값을 저장한다. 그리고 계속 검사한다. 왜냐하면 빈칸이고 냄새가 없는 칸이 나올수도 있기 때문이다. 후자의 경우가 더 우선순위가 높으므로 검사를 멈추면 안된다. (4방향 중  또 내 냄새와 같은 칸이 나오면 그 값은 그냥 건너 뛴다. 이미 우선순위에 의해 이동할 위치가 정해졌으므로)

 

돌면서 빈칸이고 냄새가 없는 칸이 나오면 현재 칸은 상어가 없는것으로 표시하고 이 경우가 가장 우선순위가 높으므로 다른 방향을 조사할 필요 없이 검사를 중단한다.

 

 

2단계 

CASE 1 

위에서 상어가 없고, 냄새도 없는 칸을 찾은 경우에는 해당 상어의 위치 정보를 바꿔주고(이차 배열은 아직 안바꿈), 임시 벡터를 만들어서 해당 칸에 상어 번호를 넣는다. (나중에 가장 작은 상어만 남겨놓고 다 내보내기 위함)

 

CASE 2

CASE1 에 해당하지 못할 경우에는 내냄새와 같은 칸으로 이동해야 한다. 1단계에서 값을 저장해놓았으므로 상어 객체 정보를 갱신한다.

 

CASE 3

이외 상황은 문제에서 조건으로 주어지지 않았으므로 고려하지 않아도 된다.

 

 

 

3단계

M개의 상어에 대해 어디 위치로 이동해야할지 조사가 다 끝났으니 정보를 갱신해야한다.

아까 위의 2단계-CASE1 에서 가장 번호가 작은 상어만 남겨놓고 나머지는 내보내는 것을 안 했으니 3단계에서 수행해준다. 임시 3차원 벡터 tmp를 돌면서 그 칸의 후보가 1이면 그냥 넣어주고, 2이상이면 상어 번호들을 비교해서 가장 최소 번호 상어만 남기고 다 지운다. (goOut()에서 수행한다.)

또한 내보낸 상어들 수를 카운트해서 처음 상어에서 빼준다. 

 

 

4단계

이제 냄새를 1씩 감소해준다. 이때 주의할 점은 상어가 있는 칸을 제외하고 1을 감소시켜줘야 한다.

 

 

 

위 단계들을 반복하면서 남은 상어가 1마리인데 그 상어 번호가 1일 때까지 반복하며, 1000번 넘게 반복하면 스탑한다.

 

 

 

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

using namespace std;


class Shark {
public:
	int r, c, d;
	int dirArr[5][5];
	bool live;
	Shark() {}
	Shark(int _r, int _c, int _d, int _dirArr[5][5], bool _live) {
		r = _r;
		c = _c;
		d = _d;
		for (int i = 1; i <=4; i++) {
			for (int j = 1; j<=4; j++) {
				dirArr[i][j] = _dirArr[i][j];
			}
		}
		live = _live;
	}
};
pair<int, pair<int, int>> sharkMap[21][21];	//현재 상어 번호
Shark sharkArr[400];
int N, M, k;

//x, 위 아 왼 오
int dr[5] = { 0,-1,1,0,0 };
int dc[5] = { 0,0,0,-1,1 };


//1초 지나서 k감소
void decreaseK() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (sharkMap[i][j].first==-1 && sharkMap[i][j].second.second > 0) {		//상어가 떠난 자리에 냄새가 남아있는 칸이면
				sharkMap[i][j].second.second -= 1;
			}
		}
	}

}
void goOut(vector<int> vec, int left, int nr, int nc) {		//vec 중에서 left 빼고 다 내보내기
	//sharkArr 처리
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] != left) {	//나머지들 내보내기
			sharkArr[vec[i]].live = false;
		}
	}
	//sharkMap 처리
	sharkMap[nr][nc] = make_pair(left, make_pair(left, k));
}



int main() {

	cin >> N >> M >> k;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int sharkNum; cin >> sharkNum;
			if (sharkNum != 0) {
				sharkMap[i][j] = make_pair(sharkNum, make_pair(sharkNum, k));
				sharkArr[sharkNum].r = i;
				sharkArr[sharkNum].c = j;
				sharkArr[sharkNum].live = true;
			}
			else {
				sharkMap[i][j] = make_pair(-1, make_pair(-1, 0));
			}
		}
	}
	
	//상어 m 마리의 방향
	for (int i = 1; i <= M; i++) {
		int dir; cin >> dir;
		sharkArr[i].d = dir;
	}

	//상어 m 마리의 우선순위
	for (int m = 1; m <= M; m++) {

		for (int i = 1; i <= 4; i++) {
			for (int j = 1; j <= 4; j++) {
				cin >> sharkArr[m].dirArr[i][j];
			}
		}
	}



	int leftSharkCnt = M;		//격자 안에 남아있는 상어 수 
	int sec = 0;

	while (sec <= 1000) {

		if (leftSharkCnt == 1 && sharkArr[1].live == true) break;


		vector<int> tmp[21][21];	//움직이고나서의 상어 번호 저장 
		//상어 1번부터 M번까지 동시에 이동
		for (int s = 1; s <= M; s++) {
			if (sharkArr[s].live == false) continue;	//이미 나간 상어

			pair<int, int> sameSmellLoc = make_pair(-1, -1);
			int toSameSmellmoveDir = 0;
			int curR = sharkArr[s].r;
			int curC = sharkArr[s].c;
			int curD = sharkArr[s].d;


			//아무것도 없는 빈 칸(k<=0) -> 자신의 냄새 있는 칸 
			bool isEmpty = false;
			int nr, nc, nd;

			//1단계
			for (int i = 1; i <= 4; i++) {
				nd = sharkArr[s].dirArr[curD][i];		
				nr = curR + dr[nd];
				nc = curC + dc[nd];
				if (nr <= 0 || nr > N || nc <= 0 || nc > N) continue;

				if (sharkMap[nr][nc].first == -1 && sharkMap[nr][nc].second.second<=0) {		//빈칸이고 냄새 없음 
					
					isEmpty = true; 
					sharkMap[curR][curC].first = -1;									//현재칸 상어 없애기
					break;
				}
				else if (sharkMap[nr][nc].second.second >= 0 && sharkMap[nr][nc].second.first == s) {
					if (sameSmellLoc.first == -1) {	//내냄새와 같은 첫 위치만 저장
						sameSmellLoc.first = nr;
						sameSmellLoc.second = nc;
						toSameSmellmoveDir = nd;
					}
				}

			}

			//2단계
			if (isEmpty == false) {
				//위에서 저장한 내 냄새가 있는 칸으로 이동 
				sharkMap[sameSmellLoc.first][sameSmellLoc.second] = make_pair(s, make_pair(s, k));
				sharkArr[s].r = sameSmellLoc.first;
				sharkArr[s].c = sameSmellLoc.second;
				sharkArr[s].d = toSameSmellmoveDir;

				
				sharkMap[curR][curC].first = -1;					//이동 후 현재 위치 있던거 삭제
			}

			else {
				sharkArr[s].r = nr;		sharkArr[s].c = nc;		sharkArr[s].d = nd;
				tmp[nr][nc].push_back(s);			//일단 후보들 킵
			}
		}


		//3단계 
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (tmp[i][j].size() == 0) continue;
				else if (tmp[i][j].size() == 1) {
					int shark_num = tmp[i][j][0];
					sharkMap[i][j] = make_pair(shark_num, make_pair(shark_num, k));
				}
				else {	//2개 이상
					int mini = 1000;
					for (int k = 0; k < tmp[i][j].size(); k++) {
						if (mini > tmp[i][j][k]) mini = tmp[i][j][k];
					}
					goOut(tmp[i][j], mini, i, j);	//(i,j)에 mini번 상어만 남기기
					leftSharkCnt = leftSharkCnt - tmp[i][j].size() + 1;	//한개만 빼고 다 내보냄

				}
			}
		}

		//4단계
		//상어 이동 완료 후 
		decreaseK();


		//모든 상어 동시에 이동 후 sec 증가
		sec++;


	}

	if (sec > 1000) cout << -1;
	else cout << sec;


	return 0;
}