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

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 아기 상어는 매초 상하좌우로 1칸을 이동할 수 있다. 단, 자신보다 큰 물고기가 있는 칸은 갈 수 없다.
2. 아기 상어는 자신보다 작은 물고기를 잡아먹을 수 있다.
3. 아기 상어는 가장 가까운 물고기를 잡아먹으러 간다. 단, 거리가 같다면 가장 위쪽 그리고 가장 왼쪽에 있는 물고기를 잡아먹으러 간다.
4. 잡아먹으러 갈 수 있는 물고기가 없다면, 엄마를 부른다.(끝난다)
5. 위 조건들을 순서대로 BFS방식으로 코드를 짜면 된다. 3번의 조건은 가장 가까운 물고기가 2마리 이상이라면 모든 물고기 중 가장 위쪽에 있고 가장 왼쪽에 있는 물고기를 판별하여 먹으러가게하면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int N, M, sx, sy, sharkSize = 2;
int next_x[] = {-1, 0, 0, 1};
int next_y[] = {0, -1, 1, 0};
vector<vector<int> > MAP;

void input() {
    cin >> N;
    for (int x = 0; x < N; x++) {
        vector<int> temp;
        for (int y = 0; y < N; y++) {
            int num;
            cin >> num;
            temp.push_back(num);
            if (num == 9) {
                sx = x;
                sy = y;
                temp[y] = 0;
            }
        }
        MAP.push_back(temp);
    }
}

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

vector<int> bfs(int x, int y, bool visit[20][20]) {
    queue<pair<int, int> > q;
    q.push({x, y});
    visit[x][y] = true;

    vector<int> answer;
    vector<pair<int, int> > tempAnswer;
    bool isEnd = false;
    int cnt = 0;

    while (!q.empty()) {
        int q_size = q.size();

        for (int i = 0; i < q_size; i++) {
            int cur_x = q.front().first, cur_y = q.front().second;
            q.pop();

            for (int j = 0; j < 4; j++) {
                int nx = cur_x + next_x[j], ny = cur_y + next_y[j];
                if (nx > -1 && ny > -1 && nx < N && ny < N && !visit[nx][ny]) {
                    if (MAP[nx][ny] > 0 && MAP[nx][ny] < sharkSize) {
                        isEnd = true;
                        tempAnswer.push_back({nx, ny});
                        // answer.push_back(nx);
                        // answer.push_back(ny);
                        // answer.push_back(cnt + 1);
                        // MAP[nx][ny] = 0;
                        // return answer;
                    } else if (MAP[nx][ny] == 0 || MAP[nx][ny] == sharkSize) {
                        visit[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
        }
        cnt++;
        if (isEnd) {
            sort(tempAnswer.begin(), tempAnswer.end(), compare);
            x = tempAnswer[0].first;
            y = tempAnswer[0].second;
            answer.push_back(x);
            answer.push_back(y);
            answer.push_back(cnt);
            MAP[x][y] = 0;
            return answer;
        }
    }
    return answer;
}

int sol() {
    int cnt = 0, x = sx, y = sy, need = 2;
    bool visit[20][20];

    while (1) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visit[i][j] = false;
            }
        }
        vector<int> answer = bfs(x, y, visit);
        if (answer.empty()) break;

        cnt += answer[2];
        x = answer[0];
        y = answer[1];
        need--;
        if (need == 0) {
            sharkSize++;
            need = sharkSize;
        }
    }
    return cnt;
}

int main() {
    input();
    cout << sol();
    return 0;
}

---

🤔 문제 후기

BFS인데, 조건이 있었다. 처음에 예제 4번이 60이 안나왔는데, 조건에 맞게 간다고 생각했지만, 사실 북서동남 이런 순서는 상관이 없었던 것을 질문 게시판의 예시를 보고 알았다. 우선 처음에 북서 2가지 방향으로 갈 수 있는 길이 존재할 때, 북서동남 순으로 탐색하면 같은 거리게 있는 먹이일 경우 무조건 처음에 북으로 시작한 곳이 선택된다는 것을 알았다. 그래서 일단 코드적으로는 조금 더러워지지만, 기존 코드를 주석을 하고 isEnd를 만들어서 해결했다. 앞으로 구현 관련 문제는 조건을 생각하고, 예외를 먼저 생각하는 능력을 길러야 이런 오류가 생기지 않을 것 같고, 내가 예외가 생길 것 같은 예제를 생각해봐야겠다.