#include <iostream>
#include <cstring> // memset, memcpy
#include <vector>
using namespace std;
int N, M, k;
int A[21][21]; // 상어 위치 표시
int temp[21][21] = {0}; // 상어 이동 후 임시 저장
struct MAP{
int sharkNum; // 상어 번호
int cnt; // 냄새 cnt
};
MAP check[21][21] = {0}; // 좌표에 따른 상어 냄새 정보
// 우선순위 1 2 3 4 위, 아래, 왼쪽, 오른쪽
struct SHARK {
int y; int x;
int dir; // 현재 방향
int pri[5][4]; // 방향 우선순위
bool live; // 상어 쫓겨남 여부
};
SHARK shark[401]= {0};
// 우선순위 1 2 3 4 위, 아래, 왼쪽, 오른쪽
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
int rest; // 남은 상어 수
int sec = 0; // 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력
void sharkMove(){
// 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다.
sec++;
for(int i = 1; i <= M; i++){
int x = shark[i].x;
int y = shark[i].y;
int d = shark[i].dir;
bool flag = false; // 냄새 없는 칸에서 이동했는지 여부 체크
// 쫓겨난 상어면 탐색 x
if(!shark[i].live){
continue;
}
for(int j = 0; j < 4; j++){
// 상어 i의 방향 d일 때
// 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다.
// 우선순위에 따라서 탐색하게 했으니까 가능한 경우 바로 이동시키면 됨
int nd = shark[i].pri[d][j];
int nx = x + dx[nd];
int ny = y + dy[nd];
// 맵에서 벗어난 경우 패스
if(nx < 0 || ny < 0 || nx >= N || ny >= N){
continue;
}
// 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다.
if(check[ny][nx].cnt == 0){
// 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면,
// 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
flag = true;
// 이미 이동한 상어 없는 경우 그냥 값 집어넣음
if(temp[ny][nx] == 0){
temp[ny][nx] = i;
shark[i].x = nx; shark[i].y = ny; // 상어 위치 변경
shark[i].dir = nd;
} else {
// 이미 더 강한 상어 존재하는 경우
// 강한 상어부터 반복문 돌기 때문에 temp에 값 있으면 더 강한 상어이다
rest--;
shark[i].live = false; // 쫓겨남 표시
}
break;
}
}
if(!flag){
// 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다.
for(int j = 0; j < 4; j++){
int nd = shark[i].pri[d][j];
int nx = x + dx[nd];
int ny = y + dy[nd];
if(nx < 0 || ny < 0 || nx >= N || ny >= N){
continue;
}
if(check[ny][nx].sharkNum == i){
if(temp[ny][nx] == 0){
temp[ny][nx] = i;
shark[i].x = nx; shark[i].y = ny;
shark[i].dir = nd;
} else {
rest--;
shark[i].live = false;
}
break;
}
}
}
}
// 냄새 -1 해주기 : 상어 이동 끝난 뒤에
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(check[i][j].cnt > 0){
check[i][j].cnt--;
}
// 냄새 없어진 경우
if(check[i][j].cnt == 0){
check[i][j].sharkNum = 0; // 냄새 남긴 상어 정보도 삭제해주기
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
// 상어 있는 경우
if(temp[i][j] != 0){
check[i][j].sharkNum = temp[i][j];
check[i][j].cnt = k;
}
}
}
memcpy(A, temp, sizeof(A)); // 이동 후 결과 맵에 저장
memset(temp, 0, sizeof(temp)); // 이동 후 맵 초기화
}
int main(){
scanf("%d %d %d", &N, &M, &k);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
scanf("%d", &A[i][j]);
if(A[i][j] != 0){
// 상어 위치 저장
shark[A[i][j]].x = j;
shark[A[i][j]].y = i;
shark[A[i][j]].live = true; // 상어 살아있음을 표시
// 상어 냄새
check[i][j].sharkNum = A[i][j];
check[i][j].cnt = k; // 냄새 k번 이동하면 사라짐
}
}
}
// 각 상어의 방향이 차례대로 주어진다
for(int i = 1; i <= M; i++){
scanf("%d", &shark[i].dir);
}
// 각 상어의 방향 우선순위
for(int i = 1; i <= M; i++){
// 위 : 1부터 시작하기 때문에
for(int j = 1; j <= 4; j++){
for(int k = 0; k < 4; k++){
scanf("%d", &shark[i].pri[j][k]);
}
}
}
rest = M;
// 상어 1마리 초과 남아있는 경우
while(rest > 1){
sharkMove();
// 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
if(sec > 1000){
printf("-1");
return 0;
}
}
printf("%d", sec);
return 0;
}
처음으로 아예 문제 힌트조차 얻지 않고 그냥 혼자 힘으로 풀어낼 수 있었던 문제! 청소년 상어와 비슷하지만 아무튼 슬슬 감을 잡아가는 것 같아서 너무 뿌듯하다.
이렇게 그림을 코드로 표현할 수 있다는 것에 뿌듯하다.
상어의 위치를 저장하는 2차원 배열 A와
이동하는 상어를 저장하는 배열 temp,
상어들의 냄새 정보를 저장하는 배열 check
이렇게 3 배열을 사용하여 문제를 풀었다.
상어의 번호가 작은 쪽부터 반복문을 돈다. 쫓겨난 상어의 경우에는 탐색을 하지 않는다.
때문에 상어를 이동시켜 temp 배열에 저장시킬 때, temp의 해당 좌표에 이미 다른 상어가 위치하는 경우에는 더 강한 상어이므로 그 위치로 이동할 상어를 쫓아내면 된다.
방향에 따른 우선순위의 순서를 저장해두었으므로 그냥 for문을 돌면서 우선순위의 순서대로 탐색을 해준다.
우선적으로 빈칸으로 이동하고, 만약에 빈칸으로 이동을 못할 경우에는 자신의 냄새가 묻은 칸으로 이동한다는 것을 잊으면 안된다. 때문에 flag로 이동여부를 체크하였다.
상어 이동이 끝난 후에 냄새를 하나씩 감소시켜주어야한다.
그리고 새롭게 이동한 상어의 냄새 정보를 저장시켜준다.
상어는 1마리 남으면 종료(1번 상어가 항상 마지막에 남게 된다)이므로 상어가 쫓겨날때마다 전역변수 -1을 하여 반복문을 돌도록 했다. 이러한 경우 추가적인 별도 상어의 생존여부를 체크할 필요가 없다.
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int N, M, k;
int A[21][21];
int temp[21][21] = {0};
struct MAP{
int sharkNum;
int cnt;
};
MAP check[21][21] = {0};
struct SHARK {
int y; int x;
int dir;
int pri[5][4];
bool live;
};
SHARK shark[401]= {0};
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
int rest;
int sec = 0;
void sharkMove(){
sec++;
for(int i = 1; i <= M; i++){
int x = shark[i].x;
int y = shark[i].y;
int d = shark[i].dir;
bool flag = false;
if(!shark[i].live){
continue;
}
for(int j = 0; j < 4; j++){
int nd = shark[i].pri[d][j];
int nx = x + dx[nd];
int ny = y + dy[nd];
if(nx < 0 || ny < 0 || nx >= N || ny >= N){
continue;
}
if(check[ny][nx].cnt == 0){
flag = true;
if(temp[ny][nx] == 0){
temp[ny][nx] = i;
shark[i].x = nx; shark[i].y = ny;
shark[i].dir = nd;
} else {
rest--;
shark[i].live = false;
}
break;
}
}
if(!flag){
for(int j = 0; j < 4; j++){
int nd = shark[i].pri[d][j];
int nx = x + dx[nd];
int ny = y + dy[nd];
if(nx < 0 || ny < 0 || nx >= N || ny >= N){
continue;
}
if(check[ny][nx].sharkNum == i){
if(temp[ny][nx] == 0){
temp[ny][nx] = i;
shark[i].x = nx; shark[i].y = ny;
shark[i].dir = nd;
} else {
rest--;
shark[i].live = false;
}
break;
}
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(check[i][j].cnt > 0){
check[i][j].cnt--;
}
if(check[i][j].cnt == 0){
check[i][j].sharkNum = 0;
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(temp[i][j] != 0){
check[i][j].sharkNum = temp[i][j];
check[i][j].cnt = k;
}
}
}
memcpy(A, temp, sizeof(A));
memset(temp, 0, sizeof(temp));
}
int main(){
scanf("%d %d %d", &N, &M, &k);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
scanf("%d", &A[i][j]);
if(A[i][j] != 0){
shark[A[i][j]].x = j;
shark[A[i][j]].y = i;
shark[A[i][j]].live = true;
check[i][j].sharkNum = A[i][j];
check[i][j].cnt = k;
}
}
}
for(int i = 1; i <= M; i++){
scanf("%d", &shark[i].dir);
}
for(int i = 1; i <= M; i++){
for(int j = 1; j <= 4; j++){
for(int k = 0; k < 4; k++){
scanf("%d", &shark[i].pri[j][k]);
}
}
}
rest = M;
while(rest > 1){
sharkMove();
if(sec > 1000){
printf("-1");
return 0;
}
}
printf("%d", sec);
return 0;
}