[BOJ 16236 // C++] 아기 상어

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16236번 문제인 아기 상어이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16236

16236번: 아기 상어

글쓴이는 이 문제를 아기상어가 먹을 수 없는 물고기를 벽으로 생각하고 BFS를 하여 "가장 거리가 가까운 먹을 수 있는  중 우선순위에 맞는 물고기"를 탐색해나가는 방식으로 풀었다.

이 문제를 풀면서, 코드를 깔끔히 사용하고, 반복되는 부분을 함수로 정의하거나 반복문을 활용하여 줄이는 연습을 더 해야겠다는 생각이 들었다.

 

글쓴이의 코드의 작동은 다음과 같이 이루어진다.

1) N by N 공간을 읽어온다.

1-1) 먹을 수 있는 물고기 벡터를 만든다.

1-2) 크기별 물고기 벡터를 만든다.

 

2) 아기 상어의 크기보다 큰 숫자가 적힌 칸을 벽의 조건으로 생각하고, bfs로 아기상어의 위치에서 가장 가까운 거리의 "먹을 수 있는 물고기"들을 찾는다:

2-1) bfs를 하면서 "지금까지 탐색하던 점보다 멀어진 거리의 점"을 밟았을 때, "먹을 수 있는 물고기" 벡터에 있는 물고기가 놓인 지점을 (문제 조건에 적힌 순서대로) 방문했는지 순서대로 확인해본다.

    2-1-1) 물고기를 발견한다면 출력할 답에 현재 물고기의 거리를 더한다. 물고기의 위치를 아기상어의 새로운 위치로 하고, 먹을 수 있는 물고기 벡터에서 해당 물고기를 지운다.

    2-1-2) 이 물고기를 먹어서 물고기가 커질 수 있는지 확인한다. 물고기가 커질 수 있다면 물고기의 크기를 키우고, 새로 먹을 수 있게 된 물고기들을 먹을 수 있는 물고기 벡터에 집어넣는다.

2-2) 먹을 수 있는 물고기가 아기 상어가 갈 수 있는 가장 먼 칸에만 존재할 수도 있다. 이 경우 2-1의 조건을 만족시키지 못해 빠져나가므로, 이 경우를 붙잡아 다시 위의 과정을 해준다.

2-3) 2-2를 했는데도 먹을 수 있는 물고기가 없었다면 더 이상 먹을 수 있는 물고기가 없는 것이다. 탐색을 종료한다.

 

아래는 제출한 소스코드이다. 매우 길어 접어둔다.

※ 많이 지저분하니 읽지 않는 것을 권장한다. ※

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

using std::cin;
using std::cout;
using std::vector;
using std::pair;
using std::queue;

int N;
pair<int, int> babyshark;
int babysharksize = 2;
int babysharkexp = 0;
int ans = 0;
int graph[21][21];
int dist[21][21];

vector<pair<int, int>> delicious;
vector<pair<int, int>> size2;
vector<pair<int, int>> size3;
vector<pair<int, int>> size4;
vector<pair<int, int>> size5;
vector<pair<int, int>> size6;
vector<pair<int, int>>::iterator iter;
vector<pair<int, int>>::iterator sizereader;

int bfs() {
    queue<pair<int, int>> que;
    que.push(babyshark);
    bool notbreaked = true;
    for (int i = 0;i < 21;i++) {
        for (int j = 0;j < 21;j++) {
            dist[i][j] = 0;
        }
    }
    int currentdist = 0;
    bool ifcheck = false;
    while (!que.empty()) {
        pair<int, int> nextpoint;
        pair<int, int> current = que.front();
        que.pop();
        if (current.first != 0) {
            if (graph[current.first - 1][current.second] <= babysharksize and dist[current.first - 1][current.second] == 0) {
                nextpoint = { current.first - 1, current.second };
                que.push(nextpoint);
                dist[nextpoint.first][nextpoint.second] = dist[current.first][current.second] + 1;
            }
        }
        if (current.second != 0) {
            if (graph[current.first][current.second - 1] <= babysharksize and dist[current.first][current.second - 1] == 0) {
                nextpoint = { current.first, current.second - 1 };
                que.push(nextpoint);
                dist[nextpoint.first][nextpoint.second] = dist[current.first][current.second] + 1;
            }
        }
        if (current.first != N - 1) {
            if (graph[current.first + 1][current.second] <= babysharksize and dist[current.first + 1][current.second] == 0) {
                nextpoint = { current.first + 1, current.second };
                que.push(nextpoint);
                dist[nextpoint.first][nextpoint.second] = dist[current.first][current.second] + 1;
            }
        }
        if (current.second != N - 1) {
            if (graph[current.first][current.second + 1] <= babysharksize and dist[current.first][current.second + 1] == 0) {
                nextpoint = { current.first, current.second + 1 };
                que.push(nextpoint);
                dist[nextpoint.first][nextpoint.second] = dist[current.first][current.second] + 1;
            }
        }
        bool chk = false;
        if (dist[current.first][current.second] != currentdist) {
            currentdist++;
            for (iter = delicious.begin();iter != delicious.end();iter++) {
                pair<int, int> x = *iter;
                if (dist[x.first][x.second] != 0 and dist[x.first][x.second] < currentdist) {
                    ans += dist[x.first][x.second];
                    babyshark.first = x.first;
                    babyshark.second = x.second;
                    delicious.erase(iter);
                    babysharkexp++;
                    if (babysharkexp == babysharksize) {
                        babysharksize++;
                        babysharkexp = 0;
                        if (babysharksize == 3) {
                            for (sizereader = size2.begin();sizereader != size2.end();sizereader++) {
                                pair<int, int> y = *sizereader;
                                delicious.push_back(y);
                            }
                        }
                        if (babysharksize == 4) {
                            for (sizereader = size3.begin();sizereader != size3.end();sizereader++) {
                                pair<int, int> y = *sizereader;
                                delicious.push_back(y);
                            }
                        }
                        if (babysharksize == 5) {
                            for (sizereader = size4.begin();sizereader != size4.end();sizereader++) {
                                pair<int, int> y = *sizereader;
                                delicious.push_back(y);
                            }
                        }
                        if (babysharksize == 6) {
                            for (sizereader = size5.begin();sizereader != size5.end();sizereader++) {
                                pair<int, int> y = *sizereader;
                                delicious.push_back(y);
                            }
                        }
                        if (babysharksize == 7) {
                            for (sizereader = size6.begin();sizereader != size6.end();sizereader++) {
                                pair<int, int> y = *sizereader;
                                delicious.push_back(y);
                            }
                        }
                        sort(delicious.begin(), delicious.end());
                    }
                    chk = true;
                    ifcheck = true;
                    break;
                }
            }
        }
        if (chk) {
            notbreaked = false;
            break;
        }
        if (current == babyshark) {
            dist[current.first][current.second] = 1000000000;
        }
    }
    if (!ifcheck) {
        for (iter = delicious.begin();iter != delicious.end();iter++) {
            pair<int, int> x = *iter;
            if (dist[x.first][x.second] == currentdist and currentdist != 0) {
                ans += dist[x.first][x.second];
                babyshark.first = x.first;
                babyshark.second = x.second;
                delicious.erase(iter);
                babysharkexp++;
                if (babysharkexp == babysharksize) {
                    babysharksize++;
                    babysharkexp = 0;
                    if (babysharksize == 3) {
                        for (sizereader = size2.begin();sizereader != size2.end();sizereader++) {
                            pair<int, int> y = *sizereader;
                            delicious.push_back(y);
                        }
                    }
                    if (babysharksize == 4) {
                        for (sizereader = size3.begin();sizereader != size3.end();sizereader++) {
                            pair<int, int> y = *sizereader;
                            delicious.push_back(y);
                        }
                    }
                    if (babysharksize == 5) {
                        for (sizereader = size4.begin();sizereader != size4.end();sizereader++) {
                            pair<int, int> y = *sizereader;
                            delicious.push_back(y);
                        }
                    }
                    if (babysharksize == 6) {
                        for (sizereader = size5.begin();sizereader != size5.end();sizereader++) {
                            pair<int, int> y = *sizereader;
                            delicious.push_back(y);
                        }
                    }
                    if (babysharksize == 7) {
                        for (sizereader = size6.begin();sizereader != size6.end();sizereader++) {
                            pair<int, int> y = *sizereader;
                            delicious.push_back(y);
                        }
                    }
                    sort(delicious.begin(), delicious.end());
                }
                notbreaked = false;
                break;
            }
        }
    }

    if (notbreaked) return 0;
    else return 1;
}

int main()
{
    cin >> N;
    int x;
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cin >> x;
            if (x == 1) delicious.push_back({ i,j });
            if (x == 2) size2.push_back({ i,j });
            if (x == 3) size3.push_back({ i,j });
            if (x == 4) size4.push_back({ i,j });
            if (x == 5) size5.push_back({ i,j });
            if (x == 6) size6.push_back({ i,j });
            if (x == 9) {
                babyshark = { i,j };
                graph[i][j] = 0;
            }
            else graph[i][j] = x;
        }
    }
    for (int i = 0; i < N; i++) {
        graph[i][N] = 1000000000;
    }
    for (int j = 0; j < N; j++) {
        graph[N][j] = 1000000000;
    }

    bool chk = 1;
    while (chk) {
        chk = bfs();
    }

    cout << ans;

    return 0;
}