[ 백준 16236 ] 아기상어 (c/c++)

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

 

 

[ 문제 요약 ]

기본 크기가 2인 아기 상어는 자기보다 같거나 작은 물고기를 먹을 수 있다. 만약 자기 크기만큼 물고기를 먹었다면 크기가 1 커진다. 이동하는 데 1초가 걸릴 때 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

 

[ 문제 풀이 ]

1. 아직 상어가 물고기를 안 먹었다면 근처의 물고기를 먹는다.

2. 만약 물고기를 먹을 수 없다면 1칸 이동한 뒤 다시 확인한다.

3. 물고기를 먹었다면 현재 상어의 위치로 저장한다.

4. 물고기를 먹은 횟수를 세면서 만약 크기와 같아지면 크기를 하나 늘이고 카운트를 초기화한다.

5. 만약 BFS를 벗어났는데도 먹지 못했다면 종료한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[22][22];
int dx[] = {0, -1, 1, 0};
int dy[] = {-1, 0, 0, 1};
int bx, by;
int result = 0;
int cnt = 0;
int sz = 2;
bool stop = false;
bool eat = false;

void bfs(int a, int b, bool visit[][22], int shSize) {
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(a, b), 0));
    visit[a][b] = true;
    int temp;
    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second;
        if (arr[x][y] > 0 && arr[x][y] < shSize && temp == cnt) {
            if((bx > x) || (bx == x && by > y)) {
                bx = x;
                by = y;
                continue;
            }
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && !visit[nx][ny]) {
                if(arr[nx][ny] <= shSize) {
                    if(arr[nx][ny] > 0 && arr[nx][ny] < shSize && !eat) {
                        eat = true;
                        bx = nx;
                        by = ny;
                        temp = cnt + 1;
                        result += temp;
                    } else {
                        q.push(make_pair(make_pair(nx, ny), cnt + 1));
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if(arr[i][j] == 9) {
                bx = i;
                by = j;
                arr[i][j] = 0;
            }
        }
    }

    while(!stop) {
        bool visit[22][22] = {0};
        bfs(bx, by, visit, sz);
        if(eat) {
            eat = false;
            cnt += 1;
            arr[bx][by] = 0;
            if(cnt == sz) {
                sz += 1;
                cnt = 0;
            }
        } else {
            stop = true;
        }
    }
    cout << result;
    return 0;
}

 

 

 

[ 주의할 점 ]

조건을 하나하나에 주의해서 상어를 이동해야 한다.