[백준 19237][C++] 어른 상어

문제

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

 

풀이 과정

1. 상어의 상태를 저장하기 위한 방법, 냄새를 저장할 방법을 정한다.

2. 상어의 초기 상태 및 선호 방향에 대한 입력을 받는다.

3. 상어를 이동시킨다. (선호하는 방향 순서로 탐색한다.)

    이동 시 냄새가 없는 칸을 먼저 확인한다. 냄새가 없는 칸이 없다면 자신의 냄새가 남아있는 칸으로 이동한다.

4. 상어들의 이동이 끝난 뒤, 겹치는 상어를 제거한다.

5. 상어의 이동과 중복 제거를 끝낸 뒤, 현재 저장되어 있는 냄새의 지속시간을 1씩 감소시키고 상어의 위치의 칸의 정보를 업데이트한다.

6. 3-5 과정을 수행 한 뒤, 현재 남은 상어가 한 마리뿐인지 체크한다.

7. 6을 만족하면 현재까지의 반복 횟수를 출력한다. 만족하지 않는다면 3-6을 반복한다. 반복이 1000이 넘어갈 경우 -1을 출력한다.

 

 

 

세부 풀이

(1)

필자는 shark, smell 구조체를 만들어 smell은 배열로, shark는 vector로 설정하여 관리했다.

 

(2)

입력을 받을 때 map에 상어의 type의 순서대로 등장하는 것이 아니므로, 우선 map의 입력을 받은 뒤, shark를 저장하는 벡터에 map을 탐색하며 타입의 순서대로 집어넣어 준다. 왜냐하면 이후 상어의 번호의 순서대로 해당하는 값들을 입력받기 때문에 갑을 저장하는 것이 훨씬 수월해진다.

 

(3) move_shark 함수

앞에서 상어를 저장한 벡터에서 인자를 하나씩 받아 move_shark를 수행하도록 구현했다.

이 함수에서 탐색을 진행하는 순서는 입력받은 상어의 현재 방향을 기준으로 선호하는 방향 순서로 진행된다.

 

73 Line의 one.prefer [one.dir][i]를 이용하여 저장된 선호하는 방향 순서를 접근했다.

예를 들어 문제의 예시와 동일한 상황을 보면, 현재 상어 1이 바라보는 방향이 위쪽일 때, one.dir = 1의 값을 가진다. prefer [5][5]에 Input 함수에서 입력받은 대로 prefer [5] 에는  {0,2,3,1,4}가 저장되어 있을 것이다. (인덱스 사용의 편의를 위해 1부터 값을 저장했다.)

따라서 prefer [현재 바라보고 있는 방향][i]을 i=1부터 4까지 탐색하는 형태로 구현했다.

 

우선적으로 냄새가 없는 칸을 위의 순서로 탐색한 뒤, 값의 변화가 없었다면 냄새가 있는 칸 중 자신의 냄새가 있는 방향으로 이동하도록 구현했다. 이때 상어는 이전 상황에서 이동을 했으므로 반드시 4방향 중 하나는 자신의 냄새가 있는 칸이 존재한다.

 

(4) update_shark 함수

상어의 이동이 끝난 뒤, 좌표가 겹치는 상어를 찾아 is_dead 인자를 true로 만들어 주었다. (버블 소트의 탐색 방식을 적용했다.)

이후 반복에서 죽은 함수는 이동하지 않는다. 

 

(5) update_map 함수

3-4의 과정 이후 살아있는 상어들을 기준으로 map에 상어 위치에 type 값과 냄새의 지속시간을 업데이트한다.

 

(6) check_shark 함수

상어를 저장했던 벡터를 탐색하며 is_dead 인자를 확인하며 살아있는 상어의 수를 구한다. 이때 살아남은 상어의 수가 1이라면 true를 반환하고 그렇지 않은 경우 false를 반환한다.

 

(7)

3-6 과정을 while문을 통해 1000번 반복한다. 이때 check_shark를 통해 true를 반환받은 경우 현재까지의 cnt를 출력하고 return 하도록 구현했다. 만약 1000번 동안 check_shark가 true가 되는 경우가 한 번도 없다면 -1을 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>

using namespace std;

struct shark{
    int type,x,y,dir=0;
    int prefer[5][5]={0,};
    bool is_dead = false;
};

struct smell{
    int type=0, remain_smell=0;
};

int N,M,k;
const int max_n = 21;
smell map[max_n][max_n];
vector<shark> shks;


void Input(){
    cin >> N >> M >> k;
    int temp;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> temp;
            if(temp!=0){
                map[i][j].type = temp;
                map[i][j].remain_smell = k;
            }
        }
    }

    //이후 주어지는 현재 방향과 선호 방향이 상어의 type 대로 주어지므로
    //입력의 편의를 위해 상어를 순서대로 vector에 넣도록 한다.
    for(int s=1;s<=M;s++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(map[i][j].type==s){
                    shark one;
                    one.x = i; one.y = j; one.type = s;
                    shks.push_back(one);
                }
            }
        }
    }
    //타입순서대로 상어의 방향 입력
    for(int i=0;i<M;i++){
        cin >> temp;
        shks[i].dir = temp;
    }
    //타입순서대로 이동을 선호하는 방향 저장
    for(int i=0;i<M;i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                cin >> temp;
                shks[i].prefer[j][k]=temp;
            }
        }
    }
}

//1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽
int dir[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};

void move_shark(shark& one){
    bool change_flag=false;
    //우선 빈칸 부터 우선순위 기준 탐색
    for(int i=1;i<=4;i++){
        int x=one.x;
        int y=one.y;
        int newX = x+dir[one.prefer[one.dir][i]][0];
        int newY = y+dir[one.prefer[one.dir][i]][1];
        if(newX <0 || newX >=N || newY <0 || newY >= N) continue;
        if(map[newX][newY].remain_smell==0){
            change_flag = true;
            one.x = newX; one.y = newY;
            one.dir = one.prefer[one.dir][i];
            break;
        }
    }
    //빈칸에서 변경이 없었다면 본인의 냄새가 남아있는 영역을 우선순위 기준 탐색
    if(!change_flag){
        for(int i=1;i<=4;i++){
            int x=one.x;
            int y=one.y;
            int newX = x+dir[one.prefer[one.dir][i]][0];
            int newY = y+dir[one.prefer[one.dir][i]][1];
            if(map[newX][newY].type==one.type){
                one.x = newX; one.y = newY;
                one.dir = one.prefer[one.dir][i];
                break;
            }
        }
    }
}

//상어의 이동이 끝난 후 겹치는 상어들 중 작은 상어들 내보내는 함수
void update_shark(){
    for(int i=0;i<shks.size();i++){
        if(shks[i].is_dead) continue;
        for(int j=i+1;j<shks.size();j++){
            if(shks[j].is_dead) continue;
            //같은 위치에 상어가 있는 경우
            if((shks[i].x == shks[j].x) && (shks[i].y == shks[j].y)){
                if(shks[i].type > shks[j].type){
                    shks[i].is_dead=true;
                }
                else{
                    shks[j].is_dead=true;
                }
            }
        }
    }
}

void update_map(){
    //일단 map 의 남은 냄새들을 모두 1 감소
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j].remain_smell > 0) map[i][j].remain_smell--;
        }
    }
    //이후 상어가 있는 자리는 다시 k로 업데이트
    for(int i=0;i<shks.size();i++){
        if(shks[i].is_dead) continue;
        int nx = shks[i].x;
        int ny = shks[i].y;
        map[nx][ny].type = shks[i].type;
        map[nx][ny].remain_smell=k;
    }
}

bool check_shark(){
    int cnt=0;
    for(int i=0;i<shks.size();i++){
        if(!shks[i].is_dead) cnt++;
    }
    if(cnt==1) return true;
    else return false;
}

void solve(){
    int cnt=0;
    while(cnt<1000){
        cnt++;
        for(int i=0;i<shks.size();i++){
            if(shks[i].is_dead) continue;
            move_shark(shks[i]);
        }
        update_shark();
        update_map();
        if(check_shark()) {
            cout << cnt;
            return;
        }
    }
    cout << -1;
    return;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    Input();
    solve();
    return 0;
}

 

결과 및 후기

문제의 입력값인 N의 범위는 2 ≤ N ≤ 20이다. 따라서 max_n을 20으로 설정하여 배열을 사용했었는데, 틀렸습니다를 받았다. 이후 이 값을 21로 변경했더니 맞았다는 결과를 받을 수 있었다. 문제의 조건에 의하면 20개 이상의 입력이 들어오는 경우는 없다. 따라서 max_n을 20으로 설정하여 배열을 선언할 때 map [max_n][max_n]으로 선언했는데, 어디가 문제였는지 모르겠다.