[백준] 16236 아기 상어 DFS, Priority-Queue

문제 :

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

문제 설명 :

 

-> 아기 상어가 몇초 동안 물고기 잡아먹을 수 있는지 출력하시오

 

공간 n = 4

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어가 움직일 수 있는 조건 

1. 자기 주변에 인접한 물고기 && 먹을 수 있다면 가장 인접한 물고기를 먹으러 간다. 

2. 인접한 물고기가 여러 마리라면 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기 순으로 먹는다.

 

먹을 수 있는 물고기 조건 

1. 자기 크기보다 작은 물고기만 먹을 수 있다.

2. 자기 크기는 자기 크기 만큼의 물고기를 먹으면 1 증가한다.

 

분석 : 

상어의 움직임을 bfs로 돌고 q에서 {이동 거리, y, x}로 관리한다.

n x n 배열을 bfs로 탐색하는 동안 상어가 갈 수 있는 곳에 대해서만 q에 넣으며 

먹을 수 있으며 0이 아닌 칸에 대해 pq (먹을 수 있는 물고기 배열) + (그런데 상어가 먹을 순서대로 정렬된) 에 넣는다.

 

먹을 물고기가 있었다면 pq에 저장되어 for문 아래 if문이 실행될텐데 pq에 먹을 순서대로 정렬되어 있기 때문에 먹고 

그 위치에서 다시 bfs를 통해 상어를 움직이고 먹을 물고기들을 pq에 넣어 움직일 수 있다.

 

이 문제의 핵심은 pq에 물고기들을 먹을 순서대로 정렬한 우선 순위 큐를 이용한데에 있는거 같다.

문제 조건에서 거리가 가깝다면 가장 위에 있는 물고기 즉 y값이 작은 물고기를 의미하는 것이고 가장 왼쪽 물고기는 x값이 작은 물고기를 의미한다. 따라서 cmp 함수에서 거리, y 좌표, x 좌표 순으로 정렬한 물고기 우선 순위를 결정한다.

 

만약 q의 움직임이 끝났는데 먹을 물고기가 없다면 엄마 상어가 출동해야 할 차례이므로 여태 움직인 dist를 출력하고 while문을 빠져나온다!

 

c++ 코드 :

//
//  16236_babyShark.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/05.
//

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;
int arr[21][21];
int n;
int visit[21][21];
int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

using namespace std;

struct fish
{
    int dist;
    int y;
    int x;
};

struct compare
{
    bool operator()(fish a, fish b)
    {
        if (a.dist == b.dist)
        {
            if (a.y == b.y)
            {
                return a.x > b.x;
            }
            return a.y > b.y;
        }
        return a.dist > b.dist;
    }
};

void eat_fish_bfs(pair<int, int> start){
    queue<fish> q;
    q.push({0, start.first, start.second});
    
    int weight = 2; //현재 상어 몸무게
    int dist = 0; // 이동 거리
    int eatCount = 0; // 먹은 물고기 수
    
    while(true){
        priority_queue<fish, vector<fish>, compare> pq; // 조건에 맞게 물고기를 정렬한 우선 순위 큐
        
        while(!q.empty()){
            int x = q.front().x;
            int y = q.front().y;
            int curDist = q.front().dist;
            q.pop();
            for(int i = 0; i <4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if(arr[ny][nx] > weight || visit[ny][nx]) continue;
                q.push({curDist + 1, ny, nx});
                visit[ny][nx] = true;
                
                if(arr[ny][nx] < weight && arr[ny][nx] != 0){
                    pq.push({curDist + 1, ny, nx});
                }
            }
        }
        memset(visit, false, sizeof(visit));
        if(!pq.empty()){ // 먹을 물고기 남아 있다면
            int fishX = pq.top().x;
            int fishY = pq.top().y;
            int fishDist = pq.top().dist;
            pq.pop();
            
            arr[fishY][fishX] = 0;
            eatCount++;
            dist = fishDist;
            q.push({dist, fishY, fishX}); //상어 움직임
            visit[fishY][fishX] = true;
        }else{
            cout << dist << '\n';
            break;
        }
        
        if(eatCount == weight){
            weight++;
            eatCount = 0;
        }
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    pair<int, int> start;
    cin >> n;
    for(int i = 0 ; i < n; i++){
        for(int j = 0 ; j < n; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 9){
                start = {i, j};
                arr[i][j] = 0;
                visit[i][j] = true;
            }
        }
    }
    
    eat_fish_bfs(start);
    
    return 0;
}