49. SW_Test 연습 백준 어른상어

 

www.acmicpc.net/problem/19237

19237번: 어른 상어

 

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

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

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

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

우선 순위상어

↓ ← ↑ →	↓ → ← ↑	→ ← ↓ ↑	← → ↑ ↓
→ ↑ ↓ ←	↓ ↑ ← →	↑ → ← ↓	← ↓ → ↑
← → ↓ ↑	← → ↑ ↓	↑ ← ↓ →	↑ → ↓ ←
→ ← ↑ ↓	→ ↑ ↓ ←	← ↓ ↑ →	↑ → ↓ ←

 

 

입력

첫 줄에는 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 <algorithm>
using namespace std;
int smell_map[21][21];
int time_map[21][21];
int N, M, K, Scnt;
int dir[4][2] = { {-1,0} ,{1,0}, {0,-1}, {0,1} }; // 상 하 좌 우
struct Shark {
    int y, x, num, dir;
    vector <int> pri_list[4]; // 우선순위
};
bool cmp(Shark a , Shark b){
    return a.num < b.num;
}
bool cmp2(Shark a , Shark b){
    return a.num > b.num;
}
vector <Shark> shark_list; // 상어 num 순으로 정렬
void move(){
    vector <Shark> tmp_shark_list; // 살아있는 상어만 담는 list
    for(int i = 0 ; i < N ;i++){ //먼저 time_map 의 시간을 줄여준다.
        for(int j = 0 ; j< N;j++){
            if(time_map[i][j] > 0) time_map[i][j] --;
            if(time_map[i][j] == 0 && smell_map[i][j] != 0 ) smell_map[i][j] = 0;
        }
    }
    for(int i = 0 ; i < shark_list.size(); i++){ //같은 곳을 겹치게되면 번호가 낮은 상어가 덮어쓴다. (처음에 내림차순 정렬했기 떄문)
        smell_map[shark_list[i].y][shark_list[i].x] = shark_list[i].num;
        time_map[shark_list[i].y][shark_list[i].x] = K;
    }
    for(int i = 0 ; i < shark_list.size(); i++){ //같은위치의 smell_map과 상어번호가 다르다면 그상어는 죽은 상어
        if(smell_map[shark_list[i].y][shark_list[i].x] == shark_list[i].num){
            tmp_shark_list.push_back(shark_list[i]);
        }
    }
    shark_list = tmp_shark_list; //shark_list 교체
}
void update_shark_pos(){
    for(int i = 0 ; i < shark_list.size(); i++){
        Shark s = shark_list[i];
        bool flag = false;
        for(int k =0 ;k<4 ; k++){
            int nextdir = s.pri_list[s.dir][k];
            int nextY = s.y + dir[nextdir][0];
            int nextX = s.x + dir[nextdir][1];
            if(nextY < 0 || nextX < 0|| nextY >= N || nextX >= N ) continue;
            if(smell_map[nextY][nextX] == 0){
                //cout << s.num <<"냄새 안 나는곳 찾음" <<endl;
                flag = true;
                shark_list[i].y = nextY;
                shark_list[i].x = nextX;
                shark_list[i].dir = nextdir;
                break;
            }
        }
        if(flag == true) continue; // 위치 찾으면 다음 상어 업데이트
        for(int k =0 ;k<4 ; k++){
            int nextdir = s.pri_list[s.dir][k];
            int nextY = s.y + dir[nextdir][0];
            int nextX = s.x + dir[nextdir][1];
            if(nextY < 0 || nextX < 0|| nextY >= N || nextX >= N ) continue;
            if(smell_map[nextY][nextX] == s.num){
                //cout << s.num <<"나의 냄새 나는곳 찾음" <<endl;
                shark_list[i].y = nextY;
                shark_list[i].x = nextX;
                shark_list[i].dir = nextdir;
                break;
            }
        }
    }
}
void input_data() {
    cin >> N >> M >>K;
    for(int i  =0; i < N ; i++){
        for(int j = 0 ; j < N ;j++){
            int x ;
            cin >> x;
            if(x != 0){
                Shark s;
                s.y = i;
                s.x = j;
                s.num = x;
                shark_list.push_back(s);
                smell_map[i][j] = x;
                time_map[i][j] = K;
            }
        }
    }
    sort(shark_list.begin(), shark_list.end(),cmp); // 1번 상어부터 입력 되므로 오름차순 정렬 수행
    for(int i = 0 ; i < shark_list.size() ;i++){
        cin >> shark_list[i].dir;
        shark_list[i].dir--;
    }
    for(int i = 0 ; i < shark_list.size() ; i++ ){
        for(int k = 0 ; k < 4 ; k++){
            for(int j = 0; j < 4; j++){
                int dir;
                cin >> dir;
                shark_list[i].pri_list[k].push_back(dir-1);
            }
        }
    }
}
void sol(){
    update_shark_pos();
    move();
}
int main() {
    input_data();
    sort(shark_list.begin(), shark_list.end(),cmp2); // 내림차순 정렬(한번만하면됨)
    for (int T = 0; T < 1001; T++ ) {
        if (shark_list.size() == 1){
            cout << T;
            return 0;
        }
        sol();
    }
    cout << -1;
    return 0;
}