[백준] 16236번 아기상어 - C++

문제

• 백준 16236 아기상어
• https://www.acmicpc.net/problem/16236

풀이

<조건>

지도에 상어가 1마리 존재하고, 상어는 자신보다 작은 물고기를 먹을수 있다.

자신보다 큰 물고기 칸에는 갈 수 없고, 상어는 자신의 길이와 같은 수의 물고기를 먹으면 길이가 1만큼 증가한다.

상어는 가장 가까운 물고기부터 먹는다.

상어가 먹을 수 있는 모든 물고기를 먹었을 때 최소 시간을 구하는 문제이다.

조건이 까다롭지만 bfs탐색을 통해 풀수있다.

지도에서 9라는 값을 찾아 초기 시작 좌표를 획득하고 bfs탐색을 진행한다.

탐색을 통해 먹을 수 있는 물고기를 찾아 해당 좌표에 있는 값을 0(물고기를 먹었다는 뜻)으로 바꾸고 그 좌표를 기준으로 다시 bfs탐색을 수행한다.

먹을 수 있는 물고기가 여러 마리라면 가장 위에있는 물고기를 먼저먹고, 같은 열에 물고기가 물고기가 여러 마리이면 가장 왼쪽 물고기를 먹는 조건문이 필요하다.

코드

#include <iostream>
#include <queue>

using namespace std;

struct SHARK{
    int y,x,time;
};

int n;
int map[20][20];

SHARK shark;
int shark_size, shark_eat;

const int dx[]= {0,0,-1,1};
const int dy[]= {-1,1,0,0};


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int y=0;y<n;y++){
        for(int x=0;x<n;x++){
            cin >> map[y][x];
            if(map[y][x] == 9){
                shark.y=y, shark.x=x, shark.time=0;
                shark_size=2, shark_eat=0;
                map[y][x] =0;
            }
        }
    }
    bool update = true;
    while(update){
        update = false;

        bool visited[20][20] = {false,};
        visited[shark.y][shark.x] = true;
        queue<SHARK> q;
        q.push(shark);

        SHARK candi;
        candi.y = 20, candi.time = -1;
        while(!q.empty()){
            SHARK cur = q.front(); q.pop();

             if(candi.time !=-1 && candi.time < cur.time){
                break;
            }
            if(map[cur.y][cur.x] < shark_size && map[cur.y][cur.x] != 0){
                update = true;
                if(candi.y > cur.y || (candi.y == cur.y && candi.x > cur.x)){
                    candi = cur;
                }
            }

            for(int k=0;k<4;k++){
                SHARK next;
                next.y = cur.y + dy[k];
                next.x = cur.x + dx[k];
                next.time = cur.time + 1;
                if(next.y < 0 || next.y >= n || next.x <0 || next.x >=n){
                    continue;
                }
                if(visited[next.y][next.x]==false && shark_size >= map[next.y][next.x]){
                    visited[next.y][next.x] = true;
                    q.push(next);
                }
            }    
        }


        if(update){
            shark = candi;
            ++shark_eat;
            if(shark_eat == shark_size){
                ++shark_size;
                shark_eat = 0;
            }
            map[shark.y][shark.x]= 0;
        }
    }
    cout << shark.time;
}