BOJ: 아기 상어(16236) [C++]

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

 

그래프 탐색. 조건이 길게 적혀있는데

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

탐색 시 우선순위는 거리가 가까움 / 가장 위에 있음(y좌표가 최소) / 가장 왼쪽에 있음(x좌표가 최소) 에 따라 정해진다.

우선순위 큐를 사용한 BFS로 먹을 수 있는 물고기를 탐색해준다.

상어의 크기, 위치, 이동한 거리, 그에 따른 시간을 잘 다뤄주어야 할 듯하다

 

1. bfs를 통해 먹을 물고기 찾음

2. 물고기를 먹으면 그 칸으로 이동, 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기 증가, 먹힌 칸은 빈 칸으로

3. 더 먹을 물고기가 없으면 종료 (크기가 딸릴 수도, 다 먹어서 없을 수도...->먹은 물고기 수도 저장 필요)

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> ci;

int dx[4] = { 0, 0, -1, 1};
int dy[4] = { -1, 1, 0, 0}; //상하좌우

pair<int, ci> babyShark(int n, int size, ci loc, vector<vector<int>>&board){
    priority_queue<pair<int, ci>, vector<pair<int,ci>>, greater<pair<int,ci>>> pq; //먹을 수 있는 후보 물고기 저장. first(int): 거리, second(ci): 좌표(y,x)
    queue<ci> q; //좌표(y,x) 저장할 큐
    vector<vector<int>> dist(n, vector<int>(n,0)); //이동거리
    
    dist[loc.first][loc.second] = 1; //현재 상어 위치
    q.push(loc);
    
    while(!q.empty()){
        ci curr = q.front(); //현재 상어위치 가져옴
        q.pop();
        
        for(int i=0;i<4;i++){ //상하좌우 각각에 대해 bfs
            ci next = { curr.first + dy[i], curr.second + dx[i] }; //상어의 다음 위치 탐색
            if(next.first >=0 && next.first<n && next.second>=0 && next.second<n){ //보드 범위 벗어나지 않게
                if(dist[next.first][next.second]) continue; //이미 방문
                if(board[next.first][next.second] > size) continue; //물고기가 상어보다 크면 못 지나감(같으면 지나갈 수는 있음)
                //먹을 수 있는 경우
                if(board[next.first][next.second] && board[next.first][next.second] < size){
                    pq.push({dist[curr.first][curr.second], next}); //후보 물고기 우선순위큐에 푸시
                    continue;
                }
                dist[next.first][next.second] = dist[curr.first][curr.second] + 1; //한칸 이동했으므로 1 더함
                q.push(next); //상어의 다음 위치 저장
            }
        }
    }
    
    if(pq.empty()){ //후보가 될 수 있는 물고기가 없다면
        return { -1, {-1,-1} }; //-1 리턴
    }
    
    //물고기 먹기(우선순위큐 제일 앞에 있는 걸로)
    board[pq.top().second.first][pq.top().second.second] = 0; //물고기를 먹으면 빈칸이 됨
    
    return pq.top(); //dist(==혼자 돌아댕긴 시간)와 그때 위치를 리턴
}

int solution(int n, ci loc, vector<vector<int>>&board){
    int size = 2; //초기 상어크기는 2
    int cnt = 0; //먹은 물고기 수
    int t = 0; //걸린 시간
    
    board[loc.first][loc.second] = 0; //상어 초기위치 빈칸으로 설정
    
    while(true){
        pair<int, ci> baby_shark = babyShark(n, size, loc, board);
        if(baby_shark.first == -1) break; //먹을 물고기가 없으면 종료
        
        cnt++; //그렇지 않으면 물고기 하나 먹음
        t += baby_shark.first; //시간 증가
        
        if(cnt == size) { //자신의 크기와 같은 수의 물고기를 먹었으면
            size++; //상어크기 증가
            cnt = 0; //먹은 물고기 수 초기화
        }
        loc = baby_shark.second; //변경된 상어 위치
    }
    
    return t;
}


int main()
{
    int n, size;
    cin >> n;
    
    vector<vector<int>> board;
    board.assign(n, vector<int>(n, 0));
    ci shark_loc;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> board[i][j];
            if(board[i][j]==9) shark_loc = {i, j};
        }
    }
    int answer = solution(n, shark_loc, board);
    cout << answer << '\n';

    return 0;
}

 

주석을 열심히 달며 이해해보려 몸부림치기

어렵다어려워

어케푸냐이런걸

 

즐건식사