[algorithm] 백준 - 아기상어

이 문제는 삼성 SW 기출 문제이다.

 

먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

1. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

2. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

물고기를 잡아먹는 시간을 최소로 해야하므로 bfs로 탐색했다.

가장 위에 있고 가장 왼쪽에 있는 물고기를 먹어야하므로,

bfs로 탐색을 한 후 가장 위에 있고 가장 왼쪽에 있는 물고기를 찾아 그 칸으로 이동시킨다.

탐색은 더이상 먹을 물고기가 없을 때까지 반복한다.

 

while(1){
        bfs();
        if(minWeightPoint.first < n && minWeightPoint.second < n){
            answer += minWeight;
            babyShark = minWeightPoint;
            water[babyShark.first][babyShark.second] = 0;
            eating++;
            if(eating == babySharkSize){
                babySharkSize++;
                eating = 0;
            }
        }
        else{
            break;
        }
    }

 

bfs 탐색을 통해 가장 weight가 짧은 값을 구하고

가장 위에 있으면서 가장 왼쪽에 있는 물고기의 좌표를 선정한다.

 

if(water[dx][dy] != 0 && water[dx][dy] < babySharkSize){
                if(minWeight > weight[dx][dy]){
                    minWeight = weight[dx][dy];
                    minWeightPoint = {dx,dy};
                }
                else if(minWeight == weight[dx][dy]){
                    if(dx < minWeightPoint.first){
                        minWeightPoint = {dx,dy};
                    }
                    else if(dx == minWeightPoint.first && dy < minWeightPoint.second){
                        minWeightPoint = {dx,dy};
                    }
                }

 

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

반복문 내에서 먹은 개수를 세고, 그 개수가 물고기 크기만큼 됐을 땐 초기화 하는 방식으로 구현했다.

 

eating++;
            if(eating == babySharkSize){
                babySharkSize++;
                eating = 0;
            }

 

전체적인 코드는 이렇다.

 

//아기 상어
#include <iostream>
#include <queue>
using namespace std;

int water[40][40];
int n;
pair<int,int> babyShark;
int babySharkSize = 2;
pair<int,int> minWeightPoint;
int minWeight;
pair<int,int> direct[] = {{0,1},{0,-1}, {1,0}, {-1,0}};
void bfs(){
    int weight[40][40];
    bool visited[40][40];
    minWeight = 987654321;
    minWeightPoint = {42,42};
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            weight[i][j] = 0;
            visited[i][j] = false;
        }
    }
    queue<pair<int,int>> q;
    q.push(babyShark);
    visited[babyShark.first][babyShark.second] = true;
    while(!q.empty()){
        pair<int,int> node = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){
            int dx = direct[i].first + node.first;
            int dy = direct[i].second + node.second;
            if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue;
            if(water[dx][dy] > babySharkSize || visited[dx][dy] == true) continue;
            visited[dx][dy] = true;
            weight[dx][dy] = weight[node.first][node.second] + 1;
            q.push({dx,dy});
            if(water[dx][dy] != 0 && water[dx][dy] < babySharkSize){
                if(minWeight > weight[dx][dy]){
                    minWeight = weight[dx][dy];
                    minWeightPoint = {dx,dy};
                }
                else if(minWeight == weight[dx][dy]){
                    if(dx < minWeightPoint.first){
                        minWeightPoint = {dx,dy};
                    }
                    else if(dx == minWeightPoint.first && dy < minWeightPoint.second){
                        minWeightPoint = {dx,dy};
                    }
                }
            }
        }
    }
}
int main(void){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> water[i][j];
            if(water[i][j] == 9){
                babyShark = {i,j};
                water[i][j] = 0;
            }
        }
    }
    int answer = 0;
    int eating = 0;
    while(1){
        bfs();
        if(minWeightPoint.first < n && minWeightPoint.second < n){
            answer += minWeight;
            babyShark = minWeightPoint;
            water[babyShark.first][babyShark.second] = 0;
            eating++;
            if(eating == babySharkSize){
                babySharkSize++;
                eating = 0;
            }
        }
        else{
            break;
        }
    }
    cout << answer;
}