BOJ 16236 - 아기 상어

문제

공간 \(N \times N(2\le N \le 20)\)의 정보가 주어질 때 아래 조건에 맞춰 아기 상어가 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 최대 시간을 구해야 한다.

• 공간의 정보
  • 0 : 빈 칸
  • [1, 6] : 물고기 크기
  • 9 : 아기 상어의 위치
• 아기 상어의 초기 크기 : 2
• 크기가 자신을 초과하는 물고기가 있는 칸은 통과 불가
• 크기가 자신보다 작은 물고기만 먹을 수 있음
• 물고기의 크기에 상관없이 자신의 크기 번 물고기를 잡아먹으면 크기가 1 증가
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹음
  • 아기 상어는 상하좌우로 이동
  • 거리가 같은 물고기가 1마리 이상이면 가장 위에 있는 물고기 중 가장 왼쪽을 먹음
• 먹을 수 있는 물고기가 없는 경우 도움 요청

풀이

소스코드

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

using namespace std;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, si, sj, ss = 2, seat = 0, ans = 0, sp, spi, spj;
    int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
    cin >> n;
    vector<vi> ar(n, vi(n, 0)), vis;
    queue<int> eq;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> ar[i][j];
            if (ar[i][j] == 9) {
                si = i;
                sj = j;
                ar[i][j] = 0;
            }
        }
    }
    while (true) {
        sp = 400, spi = -1, spj = -1;
        vi eat;
        vis = vector<vi>(n, vi(n, 400));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (ar[i][j] != 0 && ar[i][j] < ss) eat.push_back(i * 100 + j);
        vis[si][sj] = 0;
        eq.push(si * 100 + sj);
        while (!eq.empty()) {
            int eci = eq.front() / 100, ecj = eq.front() % 100;
            eq.pop();
            for (int i = 0; i < 4; i++) {
                int eni = eci + di[i], enj = ecj + dj[i];
                if (eni > -1 && eni < n && enj > -1 && enj < n && vis[eni][enj] > vis[eci][ecj] + 1 && ar[eni][enj] <= ss) {
                    vis[eni][enj] = vis[eci][ecj] + 1;
                    eq.push(eni * 100 + enj);
                }
            }
        }
        for (int i = 0; i < eat.size(); i++) {
            int ei = eat[i] / 100, ej = eat[i] % 100;
            if (vis[ei][ej] < sp) {
                sp = vis[ei][ej];
                spi = ei;
                spj = ej;
            }
        }
        if (spi != -1) {
            ans += sp;
            seat++;
            if (seat == ss) {
                ss++;
                seat = 0;
            }
            ar[spi][spj] = 0;
            si = spi;
            sj = spj;
        } else
            break;
    }
    cout << ans;
    return 0;
}

풀고나서

• 40번째 줄의 탐색 조건을 처음에는 vis[eni][enj] >= vis[eci][ecj] + 1으로 설정했다가 메모리 초과가 났다.
  • 이전에 동일한 가중치로 지나친 적이 있을 경우, 등호를 넣어서 확인할 수 있는 것은 이전 경로에 포함된 정점인데, 이 정점은 이전 경로에 포함되었을 때의 거리가 더 짧기 때문에 비교할 필요가 없다.