[19237번 어른 상어] - C++

[19237번 어른 상어]
https://www.acmicpc.net/problem/19237

[19235번 청소년 상어]
https://www.acmicpc.net/problem/19236
https://velog.io/@statco19/boj-19236

[16236번 아기 상어]
https://www.acmicpc.net/problem/16236
https://velog.io/@statco19/boj-16236

아기 상어 - 청소년 상어 - 어른 상어까지 이어지는 상어 시리즈 문제 중 마지막 문제이다. 개인적으로는 청소년 상어가 제일 까다로웠고 어른 상어-아기 상어 순으로 어려웠던 것 같다.

삼성 기출 유형답게 특별한 알고리즘 없이 구현으로 승부하는 문제였다.

풀이

현재 지도 상에 존재하는 상어의 사이즈를 나타내는 2차원 배열 sz, 현재 지도 상에 존재하는 상어의 방향을 나타내는 2차원 배열 dir, 상어가 풍기고 다니는 냄새를 표시하는 2차원 pair<int,int> 배열 smell, 상어의 현재 위치 좌표를 기록하는 1차원 pair<int,int> 배열 pos 그리고 상어마다 다른 방향 우선순위를 나타내는 3차원 배열 preference로 나누어 입력받았다.

문제에서 구현해야할 요구 사항은 다음과 같다.

1. 처음 시작할 때 냄새 뿌리기
2. 1초 동안 모든 상어가 동시에 이동한 후, 냄새 뿌리기(k번이 최대 이동 수)

if (인접한 칸 중 아무 냄새 없는 칸 존재) {

	if(가능한 칸이 1개 초과) { 상어 번호 별, 현재 보고 있는 방향 별 우선순위로 이동할 칸 결정 후 이동 }
    else { 유일하게 아무 냄새 없는 칸으로 이동 }
}
else if(자신의 냄새가 있는 칸 존재) {
	
    if(가능한 칸이 1개 초과) { 상어 번호 별, 현재 보고 있는 방향 별 우선순위로 이동할 칸 결정 후 이동 }
    else { 유일하게 자신의 냄새가 있는 칸으로 이동 }
}

3. 이동하기로 선택한 방향이 이동한 후의 방향이 됨
4. 모든 상어가 1초 동안 동시에 이동한 후, 한 칸에 여러 마리 상어가 있으면 가장 작은 번호를 가진 상어를 제외하고 탈락

주의해야 할 점은 인접한 칸 중 아무 냄새가 없는 칸이 여러 개 존재하거나, 존재하지 않아서 자신의 냄새가 있는 칸이 여러 개 존재한다면 모두 주어진 우선순위에 따라 이동할 칸을 정해줘야 한다는 점이다. 즉, 우선순위 결정이 2가지 경우에 모두 필요 시 적용되어야 한다.

동시에 모든 상어가 움직여야 하기 때문에 sz_, dir_, smell_이라는 임시 2차원 배열에 변경되는 사항을 적용시키고 다시 sz, dir, smell에 복사해주는 방식으로 동시 이동 문제를 해결하였다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
// #include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int n,m,k;
int sz[21][21];
int dir[21][21];
pair<int,int> smell[21][21];  // <size, remaining second>
pair<int,int> pos[401];  // shark location
int preference[401][5][5];  // 400 sharks at max, four directions each
int dr[] = {0,-1,1,0,0};
int dc[] = {0,0,0,-1,1};


void chooseCell(int i, int r, int c, pair<int,int> smell_[21][21], int sz_[21][21], int dir_[21][21]) {
	int direction = dir[r][c];
	int nr,nc;
	for(int d=1;d<=4;++d) {
		int preferredDir = preference[i][direction][d];
		nr = r+dr[preferredDir];
		nc = c+dc[preferredDir];

		if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n)) continue;

		pair<int,int>& p = smell[nr][nc];
		if(!p.first && !p.second) {
			if(sz_[nr][nc]) {
				if(sz[r][c] < sz_[nr][nc]) {
					sz_[nr][nc] = sz[r][c];
					dir_[nr][nc] = preferredDir;

					pos[i].first = nr;
					pos[i].second = nc;

					smell_[nr][nc].first = sz_[nr][nc];
					smell_[nr][nc].second = k;
				} else {
					pos[i].first = 0;
					pos[i].second = 0;
				}
			} else {
				sz_[nr][nc] = sz[r][c];
				dir_[nr][nc] = preferredDir;

				pos[i].first = nr;
				pos[i].second = nc;
				smell_[nr][nc].first = sz_[nr][nc];
				smell_[nr][nc].second = k;
			}
			sz_[r][c] = 0;
			dir_[r][c] = 0;

			break;
		}
	}
	return;
}

void chooseCellMySmell(int i, int r, int c, pair<int,int> smell_[21][21], int sz_[21][21], int dir_[21][21]) {
	int direction = dir[r][c];
	for(int d=1;d<=4;++d) {
		int preferredDir = preference[i][direction][d];
		int nr = r+dr[preferredDir];
		int nc = c+dc[preferredDir];

		if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n)) continue;

		pair<int,int>& p = smell[nr][nc];
		if(p.first == sz[r][c]) {  // my smell
			if(sz_[nr][nc]) {
				if(sz[r][c] < sz_[nr][nc]) {
					sz_[nr][nc] = sz[r][c];
					dir_[nr][nc] = preferredDir;

					pos[i].first = nr;
					pos[i].second = nc;
					smell_[nr][nc].first = sz_[nr][nc];
					smell_[nr][nc].second = k;
				} else {
					pos[i].first = 0;
					pos[i].second = 0;
				}
			} else {
				sz_[nr][nc] = sz[r][c];
				dir_[nr][nc] = preferredDir;

				pos[i].first = nr;
				pos[i].second = nc;
				smell_[nr][nc].first = sz_[nr][nc];
				smell_[nr][nc].second = k;
			}
			sz_[r][c] = 0;
			dir_[r][c] = 0;

			break;
		}
	}
	return;
}

void sol() {

	// 1. smell
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(sz[i][j]) {
				pair<int,int>& p = smell[i][j];
				p.first = sz[i][j];
				p.second = k;
			}
		}
	}

	// 2. move sharks & smell disperse
	int sz_[21][21], dir_[21][21];
	pair<int,int> smell_[21][21];
	copy(&smell[0][0], &smell[0][0]+441, &smell_[0][0]);
	copy(&sz[0][0], &sz[0][0]+441, &sz_[0][0]);
	copy(&dir[0][0], &dir[0][0]+441, &dir_[0][0]);
	for(int i=1;i<=m;++i) {
		int r = pos[i].first;
		int c = pos[i].second;

		int available = 0;
		int nextR, nextC;
		for(int d=1;d<=4;++d) {
			int nr = r+dr[d];
			int nc = c+dc[d];

			if(!(1<=nr&&nr<=n && 1<=nc&&nc<=n)) continue;

			pair<int,int>& p = smell[nr][nc];
			if(!p.first && !p.second) {  // no smell
				available++;
				nextR = nr;
				nextC = nc;
			}
		}

		if(available >= 1) {
			chooseCell(i,r,c,smell_,sz_,dir_);
		} else if(!available) {
			// my smell
			chooseCellMySmell(i,r,c,smell_,sz_,dir_);
		}

	}
	copy(&smell_[0][0], &smell_[0][0]+441, &smell[0][0]);
	copy(&sz_[0][0], &sz_[0][0]+441, &sz[0][0]);
	copy(&dir_[0][0], &dir_[0][0]+441, &dir[0][0]);

	for(int i=1;i<=m;++i) {
		int r = pos[i].first;
		int c = pos[i].second;

		for(int j=1;j<=n;++j) {
			for(int k=1;k<=n;++k) {
				if(j==r && k==c) continue;
				if(!smell[j][k].second) continue;
				if(smell[j][k].first == i) {
					if(--smell[j][k].second == 0) {
						smell[j][k].first = 0;
					}
				}
			}
		}
	}

	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d", &sz[i][j]);
			if(sz[i][j]) {
				int size = sz[i][j];
				pos[size].first = i;
				pos[size].second = j;
			}
		}
	}
	for(int i=1;i<=m;++i) {
		int r,c;
		r = pos[i].first;
		c = pos[i].second;

		scanf("%d", &dir[r][c]);
	}


	for(int i=1;i<=m;++i) {
		for(int j=1;j<=4;++j) {
			for(int k=1;k<=4;++k) {
				scanf("%d", &preference[i][j][k]);
			}
		}
	}

	while(ans <= 1000) {
		sol();
		ans++;

		int finish = 1;
		for(int j=2;j<=m;++j) {
			if(pos[j].first || pos[j].second) {
				finish = 0;
			}
		}

		if(finish) {
			break;
		}
	}

	ans = ans <= 1000 ? ans : -1;
	printf("%d\n", ans);
	
	return 0;
}

실행 결과