백준 16236 아기 상어 (C++)

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

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

using namespace std;

vector<vector<int>> arr;
bool visit[21][21];

int dy[4] = {-1, 0, 0, 1};
int dx[4] = {0, -1, 1, 0};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    int ans = 0;
    cin >> n;

    arr.resize(n, vector<int>(n));



    pair<int, int> eat;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                arr[i][j] = 0;
                eat = make_pair(i, j);
            }
        }
    }


    int s = 2;
    int eCnt = 0;

    while (true) {
        queue<pair<int, pair<int, int>>> q;
        fill_n(*visit, 21 * 21, false);

        q.push(make_pair(0, make_pair(eat.first, eat.second)));
        visit[eat.first][eat.second] = true;
        bool isEat = false;

        int eatTime;
        while (!q.empty()) {
            int cnt = q.front().first;
            pair<int, int> cur = make_pair(q.front().second.first, q.front().second.second);


            if (arr[cur.first][cur.second] > 0 && arr[cur.first][cur.second] < s && eatTime == cnt) {
                if (eat.first > cur.first || (eat.first == cur.first && eat.second > cur.second)) {
                    eat = cur;
                    continue;
                }
            }

            q.pop();

            for (int i = 0; i < 4; i++) {
                pair<int, int> ncur = make_pair(cur.first + dy[i], cur.second + dx[i]);


                if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < n && !visit[ncur.first][ncur.second]){
                    if (arr[ncur.first][ncur.second] <= s) {
                        if (arr[ncur.first][ncur.second] > 0 && s > arr[ncur.first][ncur.second] && !isEat) {
                            isEat = true;
                            eat = ncur;
                            eatTime = cnt + 1;
                            ans += eatTime;
                        } else {
                            q.push(make_pair(cnt + 1, make_pair(ncur.first, ncur.second)));
                            visit[ncur.first][ncur.second] = true;
                        }

                    }
                }


            }

        }
        if (isEat) {
            isEat = false;
            eCnt++;
            arr[eat.first][eat.second] = 0;
            if (eCnt == s) {
                s++;
                eCnt = 0;
            }
        } else {
            break;
        }

    }

    cout << ans;

    return 0;
}

1. 문제

아래와 같은 의미를 가진 n*n의 행렬이 주어진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 최대한 많은 양의 물고기를 먹으려는 데 다음의 제약조건이 따른다.

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

이 때 몇 초 동안 아기 상어가 물고기를 잡아먹을 수 있는 지 구하라.

2. 풀이

상당히 복잡했던 구현 문제이다. 하나씩 살펴보자.

pair<int, int> eat;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                arr[i][j] = 0;
                eat = make_pair(i, j);
            }
        }
    }

eat는 각 bfs의 시작 지점이다. 처음 아기 상어의 위치이자 각 먹이 활동이 끝나고의 위치이기도 하다. 입력을 받으면서 9를 찾으면 해당 위치는 아기 상어의 처음 위치이므로 초기화해준다.

    int s = 2;
    int eCnt = 0;

s는 아기 상어의 크기 eCnt는 상어가 먹은 물고기의 개수를 뜻한다.

queue<pair<int, pair<int, int>>> q;
        fill_n(*visit, 21 * 21, false);

        q.push(make_pair(0, make_pair(eat.first, eat.second)));
        visit[eat.first][eat.second] = true;
        bool isEat = false;

        int eatTime;
        while (!q.empty()) {
            int cnt = q.front().first;
            pair<int, int> cur = make_pair(q.front().second.first, q.front().second.second);


            if (arr[cur.first][cur.second] > 0 && arr[cur.first][cur.second] < s && eatTime == cnt) {
                if (eat.first > cur.first || (eat.first == cur.first && eat.second > cur.second)) {
                    eat = cur;
                    continue;
                }
            }

            q.pop();

            for (int i = 0; i < 4; i++) {
                pair<int, int> ncur = make_pair(cur.first + dy[i], cur.second + dx[i]);


                if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < n && !visit[ncur.first][ncur.second]){
                    if (arr[ncur.first][ncur.second] <= s) {
                        if (arr[ncur.first][ncur.second] > 0 && s > arr[ncur.first][ncur.second] && !isEat) {
                            isEat = true;
                            eat = ncur;
                            eatTime = cnt + 1;
                            ans += eatTime;
                        } else {
                            q.push(make_pair(cnt + 1, make_pair(ncur.first, ncur.second)));
                            visit[ncur.first][ncur.second] = true;
                        }

                    }
                }


            }

이후 bfs를 돌린다. 해당 bfs로 물고기를 하나씩 먹을 것이다. 하나씩 살펴보자.

 queue<pair<int, pair<int, int>>> q;
        fill_n(*visit, 21 * 21, false);

        q.push(make_pair(0, make_pair(eat.first, eat.second)));
        visit[eat.first][eat.second] = true;
        bool isEat = false;

        int eatTime;

큐를 선언하고, 각 연산에 대해 visit 배열을 초기화, 현재 위치와 현재 위치까지 오는 데 걸린 시간을 큐로 선언하고, 이를 넣어준다. eatTime는 해당 물고기를 먹는 데 까지 걸린 시간을 뜻한다.

 int cnt = q.front().first;
            pair<int, int> cur = make_pair(q.front().second.first, q.front().second.second);


            if (arr[cur.first][cur.second] > 0 && arr[cur.first][cur.second] < s && eatTime == cnt) {
                if (eat.first > cur.first || (eat.first == cur.first && eat.second > cur.second)) {
                    eat = cur;
                    continue;
                }
            }

            q.pop();

이후 여타 bfs와 마찬가지로 현재 시간과 위치를 변수로 빼고 큐에서 pop한다. 그 사이에 물고기를 먹는 규칙에 의해 걸린 시간이 같은데 더 위, 더 왼쪽에 있다면 해당 먹이를 우선으로 먹도록 수정한다.

       for (int i = 0; i < 4; i++) {
                pair<int, int> ncur = make_pair(cur.first + dy[i], cur.second + dx[i]);


                if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < n && !visit[ncur.first][ncur.second]){
                    if (arr[ncur.first][ncur.second] <= s) {
                        if (arr[ncur.first][ncur.second] > 0 && s > arr[ncur.first][ncur.second] && !isEat) {
                            isEat = true;
                            eat = ncur;
                            eatTime = cnt + 1;
                            ans += eatTime;
                        } else {
                            q.push(make_pair(cnt + 1, make_pair(ncur.first, ncur.second)));
                            visit[ncur.first][ncur.second] = true;
                        }

                    }
                }


            }

이후 상하좌우를 탐색한다. 우선 배열의 범위를 벗어나지는 않는 지 확인하고, 물고기의 크기를 비교하여 해당 공간을 넘어갈 수 있는 지 확인하고, 물고기를 먹을 수 있는 지 확인한다. 물고기를 먹을 수 있다면 해당 물고기를 먹고 그 위치와 먹는 데 걸린 시간을 초기화해준다. 이 때 물고기를 먹는 시점에서 bfs를 더 진행할 필요가 없으므로 q에 넣지는 않는다. 

 만약 지나가는 것만 허용된다면 큐에 집어넣어 연산을 계속한다.

if (isEat) {
            isEat = false;
            eCnt++;
            arr[eat.first][eat.second] = 0;
            if (eCnt == s) {
                s++;
                eCnt = 0;
            }
        } else {
            break;
        }

만약 위 bfs를 돌면서 물고기를 먹는 데 성공했다면 그 개수를 추가해주고, 먹은 물고기는 없어지므로 배열을 초기화해준다. 먹은 물고기의 개수와 아기 상어의 크기가 같다면 아기 상어의 크기를 증가시켜준다. bfs를 돌았음에도 물고기를 더 먹을 수 없다면 연산을 종료한다.

 위 연산이 끝나고 물고기를 먹는 데 걸린 총 시간을 출력하면 정답을 구할 수 있다.