16236번-아기상어

문제

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

16236번: 아기 상어

---

접근방법

1) 접근 사고

개인적으로 구현이 어려웠던 문제였습니다. 상어가 탐색하는 경우를 q 배열에  넣어주었고 경로중 문제에서 주어지는 최적의 조건을 탐색하기 위해 우선순위 큐(코드에서 pass 변수)를 사용했습니다. 물고기를 먹을 수 있는 경우도 문제에서 최적의 조건이 주어지므로 우선순위 큐를 한 개 더 사용(문제에서 pq)하여서 이동한 경우를 다시 q배열에 넣어주고 반복하였습니다. 상어가 없는 경우는 더 이상 물고기를 먹은 경우가 없는 경우이므로 탐색을 멈추게 됩니다.

 

2) 시간 복잡도

O(V + E)

 

3) 배운 점

 

4) PS

---

정답 코드

/**
 * 1.처음 아기상어의 크기는 2
 * 2.작은 물고기만 먹는게 가능
 * 3.크기가 같은거는 먹지 못하지만 통과가 가능
 * 4.자신과 같은 크기의 물고기 수를 먹으면 크기가 증가
 */
#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 21;
int board[MAX][MAX];
int my[] = {-1, 0, 1, 0};
int mx[] = {0, 1, 0, -1};
int N;
bool visited[MAX][MAX];
queue<tuple<int,int,int>> q;
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> board[i][j];
            if(board[i][j] == 9){
                q.push({i, j, 2});
                board[i][j] = 0;
            }
        }
    }
 
    int ret_cnt = 0;
    int eat_cnt = 0;
 
    while(!q.empty()){
        auto[y,x,s] = q.front();
        q.pop();
 
        memset(visited, false, sizeof visited);
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pass;
        pass.push({0, y, x});
        visited[y][x] = true;
        while(!pass.empty()){
            int passSize = pass.size();
            priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
            for(int i = 0; i < passSize; i++){
                auto[t, cy, cx] = pass.top();
                pass.pop();
 
                for(int i = 0; i < 4; i++){
                    int ny = cy + my[i];
                    int nx = cx + mx[i];
                    if(ny >= 0 && ny < N && nx >= 0 && nx < N){
                        if(!visited[ny][nx]){
                            if(board[ny][nx] <= s){
                                pass.push({t + 1, ny, nx});
                                visited[ny][nx] = true;
                                if(1 <= board[ny][nx] && board[ny][nx] < s){
                                    pq.push({ny, nx, t + 1});
                                }
                            }
                        }
                    }
                }
            }
            if(!pq.empty()){
              //  cout << "breaking point" <<"\n";
                auto[y, x, t] = pq.top();
                eat_cnt++;
                if(eat_cnt == s){
                    q.push({y, x, s + 1});
                    eat_cnt = 0;
                }
                else
                    q.push({y, x, s});
                board[y][x] = 0;
                ret_cnt += t;
                break;
            }
        }
    }
    cout << ret_cnt <<"\n";
}