[백준] 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을 출력한다.

---

풀이)

드디어 상어시리즈의 마지막 문제이다.

상어마다 방향 우선순위를 모두 이중 vector에 저장해주었고, 구조체를 2개 만들어서 푼 문제이다.

1. 상어의 번호와 냄새를 저장하는 구조체

struct shark

{

int num, smell;//상어 번호와 상어 냄새

}

2. 상어의 위치와 방향을 저장하는 구조체

struct shark_info

{

int y, x, dir;

}

번호와 냄새를 저장하는 shark 구조체는 격자의 냄새 상태를 보기 위해 사용되었다

위치와 방향을 저장하는 shark_info 구조체는 상어가 이동할 때 사용되었다.

전반적인 풀이과정은 이러하다.

시간이 1000초가 될 때까지

1. 모든 상어를 동시에 이동시킨다.

   ( 먼저 자신의 방향 우선순위 순으로 확인 -> 갈 수 있는 곳이 없으면 자신이 왔던 방향 쪽 격자로 되돌아감

     -> 갈 수 있는 곳이 있으면 shark_info 의 위치와 방향을 바꿔줌)

2. 상어의 이동이 끝났으므로 격자판의 냄새 상태를 1씩 감소시켜준다.

3. 같은 곳에 있는 상어가 있는지 확인한다.

   ( 동시에 같은 곳에 있을 경우 -> 낮은 번호의 상어만 살려두고 나머지는 격자에서 제거)

4. 격자에 남아 있는 상어의 수가 1마리인지 확인한다.

   (1마리일 경우 -> time 출력하고 stop

    여러마리일 경우 -> 1번으로 돌아가서 다시 이동 수행)

문제 그대로 구현하면 되는 문제라서, 시간이 오래걸릴뿐 어려운 문제는 아니다.

설명하기는 좀 버거워서 코드를 보면서 이해하기를 바란다.

코드)

#include <stdio.h>
#include <vector>
 
using namespace std;
 
int N, M, K;
struct shark
{
    int num, smell;//상어 번호와 상어 냄새
    shark() {
        num = 0;
        smell = 0;
    }
    shark(int num, int smell) {
        this->num = num;
        this->smell = smell;
    }
};
struct shark_info
{
    int y, x, dir;
    shark_info() {
        y = 0;
        x = 0;
        dir = 0;
    }
    shark_info(int y, int x, int dir) {
        this->y = y;
        this->x = x;
        this->dir = dir;
    }
};
vector <vector<int>> direction[401];//상어 방향 우선순위 저장
vector <vector<shark>> map;
vector <shark_info> sh_location;//상어위치 저장
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,-1,1 };
 
 
int main() {
    scanf("%d %d %d", &N, &M, &K);
    
    sh_location.resize(M + 1);
    
    //map 상황 저장
    int temp = 0;
    for (int i = 0; i < N; i++) {
        vector<shark> element(N);
        map.push_back(element);
        
        for (int j = 0; j < N; j++) {
            scanf("%d", &temp);
            if (temp > 0) {
                map[i][j] = shark(temp, K);
                sh_location[temp] = shark_info(i,j,0);
            }
        }
    }
    //상어들의 방향 저장
    for (int i = 1; i <= M; i++) {
        scanf("%d", &temp);
        sh_location[i].dir = temp;
    }
    //상어들의 방향 우선순위 저장
    vector<vector<int>> element;
    vector<int> tmp(5);
    for (int i = 0; i <= 4; i++) {
        element.push_back(tmp);
    }
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {        
            for (int k = 1; k <= 4; k++) {
                scanf("%d", &temp);
                element[j][k] = temp;
            }
        }
        direction[i] = element;
    }
 
 
    int time = 1;
    int count = M;//상어 수
    while (time <= 1000)
    {
        
        //1. 상어 이동
        for (int i = 1; i <= M; i++) {
            if (sh_location[i].dir == 0) continue;//이미 쫒겨난 상어는 pass
            int y = sh_location[i].y;
            int x = sh_location[i].x;
            int dir = sh_location[i].dir;
            //자신이 가던 방향의 우선순위대로 갈 수 있는 지 확인
            bool fail = true;
            for (int j = 1; j <= 4; j++) {
                int ny = y + dy[direction[i][dir][j]];
                int nx = x + dx[direction[i][dir][j]];
                //----- 갈 수 있는 곳이 없는 경우
                if (ny < 0 || ny >= N || nx < 0 || nx >= N) { //1.1) 격자 밖일 경우
                    continue;
                }
                if (map[ny][nx].smell > 0 ) {//1.2) 상어의 냄새가 날 경우
                    continue;
                }
 
                //----- 갈 수 있는 곳이 있는 경우
                fail = false;
                sh_location[i].y = ny;
                sh_location[i].x = nx;
                sh_location[i].dir = direction[i][dir][j];
                break;
            }
 
            if (fail) {//냄새가 나거나 막혀서 못간경우 -> 자신의 냄새를 뿌린 곳으로
                for (int j = 1; j <= 4; j++) {
                    int ny = y + dy[direction[i][dir][j]];
                    int nx = x + dx[direction[i][dir][j]];
                    if (ny < 0 || ny >= N || nx < 0 || nx >= N) { //격자 밖일 경우
                        continue;
                    }
                    if (map[ny][nx].num == i) {//자신의 냄새가 있는 곳으로 이동
                        sh_location[i].y = ny;
                        sh_location[i].x = nx;
                        sh_location[i].dir = direction[i][dir][j];
                        break;
                    }
                }
            }
        }
        
        //2. 냄새 감소
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j].smell > 0) map[i][j].smell--;
            }
        }
        //3. 겹치는 아이는 제거
        for (int i = 1; i <= M; i++) { // 낮은 번호의 상어부터
            if (sh_location[i].dir == 0) continue;//이미 쫒겨난 상어는 pass
            int y = sh_location[i].y;
            int x = sh_location[i].x;
            
            if (map[y][x].smell == K) {//낮은 번호의 상어만 살고 i번째 상어는 쫓겨남
                sh_location[i].dir = 0; // 제거 표시
                count--;
                continue;
            }
            map[y][x].num = i;
            map[y][x].smell = K;
        }
    
        //4. 상어 수 확인
        if (count == 1) {
            printf("%d", time);
            return 0;
        }
 
        time++;
    }
 
    printf("-1");
 
    return 0;
}