[백준 16236][C++] 아기 상어 (Gold5)

[문제보기]

 16236. 아기 상어

16236번: 아기 상어

 

[풀이과정]

이 문제는 같은 거리에 있는 먹을 수 있는 먹이를 찾는 것이 중요하므로 dfs보다는 bfs로 문제를 푸는 게

더 좋을 거 같아서 본인은 bfs를 가지고 문제를 풀었다.

 

일단 아기 상어의 현재 좌표, 크기, 먹이 먹은 마리의 정보를 가지고 있는 Shark 자료형을 만들어 사용을 한다.

입력값을 받으면서 아기 상어의 위치를 나타내는 9 값이 들어오면 shark 변수에 정보를 채워주면서 그 위치는 0으로 

바꿔준다. (shark 변수에 좌표를 저장하므로 9 데이터는 필요 없어짐)

 

그리고 먹을 수 있는 먹이가 있을 때까지 탐색을 해야 되므로 while() 문과 flag를 사용해 먹을 수 있는 먹이가 있으면

while() 문을 돌리고 없으면 while()문을 끝내준다.  

 

 bfs() 함수를 통해 탐색을 진행해주는데, check 배열은 확인한 곳을 중복으로 확인하지 않기 위한 배열이다. 

그리고 같은 거리에 있는 곳을 한 사이클에 전부 확인해 줘야 되므로 current_size 변수에 현재 queue에 있는 크기를 

저장하여 그만큼 for문을 진행해주고 for문이 전부 돌면 한 사이클이 끝난다. 

사이클 안에서는 bfs를 이용하여 탐색을 하면서 먹을 수 있는 먹이를 찾을 경우 vector eat 변수에 그 좌표를 넣어준다.

사이클이 끝나면 eat변수를 검사해 먹을 수 있는 먹이가 적어도 하나가 있는지 확인을 통해 있을 경우 calculation() 함수를 진행해준다. (eat변수에 먹이가 있는 경우 아기 상어 위치에서 최소 거리에 있는 먹이이므로 먹어야 한다)

 

calculation(int cnt) 함수에서 cnt는 아기 상어와 먹이와의 거리를 나타낸다. 

 -> 이 부분에서 좌표로 거리를 계산하면 중간에 갈 수 없는 곳을 신경 안 쓴 최소 거리가 나오기 때문에 bfs 연산을 하면서 거리를 계산해준다. 

 

eat 변수를 정렬해주는데 정렬 기준은 문제에서 제시한 맨 위, 맨 왼쪽부터의 기준으로 만들어준다. 정렬을 통해

맨 처음으로 오는 데이터가 아기 상어가 먹게 될 먹이가 된다. 

 

정렬 후, 이동한 거리만큼 ans_time에 더해주고, shark의 위치를 바꿔준다.  이 부분에서 먹이를 먹을 때마다 shark의 eating 변수를 1씩 증가를 하여 size와 비교를 통해 size를 증가해주는 부분도 신경 써줘야 한다. 

 

연산이 다 끝나면 먹을 수 있는 먹이의 정보를 가지고 있는 vector eat를 clear 해준다.

[소스코드]

//아기 상어
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct _shark
{
    int y;
    int x;
    int size = 2;
    int eating = 0;

}Shark;
int n, ans_time;
int map[20][20] = {0};
bool check[20][20];
Shark shark;
bool flag;
vector<pair<int, int>> eat;
pair<int, int> movdir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 

void all_print(){
    cout << "\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first == b.first)
        return a.second < b.second;

    return a.first < b.first;
}

void calculation(int cnt){
    if(eat.size() > 1){
        sort(eat.begin(), eat.end(), cmp);
    }

    ans_time += cnt;
    shark.eating++;
    map[eat[0].first][eat[0].second] = 0;
    shark.y = eat[0].first;
    shark.x = eat[0].second;

    if(shark.eating == shark.size){
        shark.size++;
        shark.eating = 0;
    }

    eat.clear();
}

void bfs(int cur_y, int cur_x){
    queue<pair<int, int>> q;
    int cnt = 1;
    q.push(make_pair(cur_y,cur_x));
    check[cur_y][cur_x] = false;

    while(!q.empty()){
        int current_size = q.size();
        for(int i=0; i<current_size; i++){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();

            for(int i=0; i<4; i++){
                int nexty = y + movdir[i].first;
                int nextx = x + movdir[i].second;

                if(nexty < 0 || n <= nexty || nextx < 0 || n <= nextx || !check[nexty][nextx]) continue;
                if(map[nexty][nextx] > shark.size) continue;

                if(map[nexty][nextx] != 0 && map[nexty][nextx] < shark.size){
                    eat.push_back(make_pair(nexty, nextx));
                }

                check[nexty][nextx] = false;
                q.push(make_pair(nexty, nextx));
            }
        }

        if(eat.size() > 0){
            flag = true;
            calculation(cnt);
            return;
        }
        cnt++;
    }
}

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
            if(map[i][j] == 9){
                map[i][j] = 0;
                shark.y = i;
                shark.x = j;
            }
        }
    }

    flag = true;
    while(flag){
        memset(check, true, sizeof(check));
        flag = false;
        bfs(shark.y, shark.x);
        //all_print();
    }

    cout << ans_time;
}

 

[해결 과정 중 실수한 부분]

처음 제출했을 때 메모리 초과가 나왔는데 코드를 다시 보니 중복 방문을 방지해주는 check 배열을 안 만들었다.

이 부분을 적용해주니 바로 정답이 나왔다.