[삼성 기출 문제] 백준 16236 아기 상어

문제 링크

어떻게 풀까?

시뮬레이션과 BFS가 함께 공존하는 혼돈의 문제입니다.

문제의 조건에 맞게 세세하게! 아주 세세하게! 잘 만들어야 합니다.

개인적으로, 시뮬레이션이면 구조체를 활용하는 방법을 추천드립니다.

문제에 굉장히 햇갈리는 조건들이 많이 있습니다.

1. 아기 상어는 입력에서 9로 주어진다. (어려운 조건은 아니지만, 이것 때문에 고생을 많이 해서 올립니다.)

2. 아기 상어는 처음에 크기가 2이다.

3. 아기 상어는 자기보다 작은 물고기만 먹을 수 있다.

4. 아기 상어는 자기보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없다.

5. 아기 상어는 다음과 같은 조건에 맞춰서 이동한다.

- 아기 상어가 먹을 수 있는 물고기가 없으면 엄마에게 도움을 요청한다! (귀엽..)

- 먹을 수 있는 물고기가 1마리라면 바로 그 물고기를 먹는다.

- 먹을 수 있는 물고기가 많다면 가장 가까운 물고기를 먹는다.

- (중요) 같은 거리에 먹을 수 있는 물고기가 많다면 가장 위에 물고기, 이 물고기도 많다면 가장 왼쪽의 물고기를 먹는다!

- 물고기를 먹으면 그 칸은 빈칸이 된다. 그리고 아기 상어는 해당 위치로 이동한다.

6. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 증가한다!

후.. 조건이 굉장히 많습니다.

우선, 구조체를 어떻게 만들지 생각해봅시다.

우선 물고기가 움직여야 하기 때문에 움직임을 처리하는 함수가 하나 필요합니다.

그리고 물고기를 먹으면 사이즈가 커질수도 있기 때문에 물고기의 크기에 해당하는 정보가 필요합니다.

물고기를 먹을때마다 아기 상어의 크기가 바로 1씩 증가하는 것이 아니라, 일정 수의 물고기를 먹어야 크기가 커집니다.

따라서, 크기가 커지려면 몇 개의 물고기를 먹어야 하는지에 관한 정보가 필요합니다.

물고기를 먹는데 고려해야할 점이 있으므로 물고기를 먹기위한 함수도 하나 만듭시다.

그리고 몇 초간 먹이를 사냥했는지도 필요하기 때문에 이에대한 정보도 필요합니다.

물고기를 먹는 처리는 쉽습니다.

만약, 먹어야하는 물고기가 0이 되면 사이즈를 1 늘리고, 다시 먹어야 하는 물고기를 사이즈로 만들어주면 됩니다.

그리고, 테스트케이스가 시작할 때 아기 상어의 크기를 2로 만들어주고, 크기가 커지기 위해 필요한 물고기도 2로 초기화합니다.

코드로 확인해 봅시다.

struct FISH {
    COD p;
    int remain;
    int dist;
    int size;
    FISH() :p({ 0,0 }), size(2), remain(2),dist(0) {}
 
    void eat() {
        remain--;
        if (remain == 0) { size++; remain = size; }
    }
};
 
bool ff(FISH &f)

아기 상어의 구조체는 이렇게 만들면 되고,

아기 상어가 먹잇감을 찾는 함수는 ff라고 합시다.

먹이를 찾으면, true를 반환하고 먹이를 찾지 못하면 false를 반환합니다.

따라서, ff가 false가 나오면 반복문을 종료하고 현재 까지 살아남은 시간을 return 해주면 됩니다.

그럼 이제 아기 상어가 물고기를 찾아 움직이는데에 필요한 조건인 3,4,5번을 함께 봅시다!

3. 아기 상어는 자기보다 작은 물고기만 먹을 수 있다.

4. 아기 상어는 자기보다 크기가 큰 물고기가 있는 칸은 지나갈 수 없다.

5. 아기 상어는 다음과 같은 조건에 맞춰서 이동한다.

- 아기 상어가 먹을 수 있는 물고기가 없으면 엄마에게 도움을 요청한다! (귀엽..)

- 먹을 수 있는 물고기가 1마리라면 바로 그 물고기를 먹는다.

- 먹을 수 있는 물고기가 많다면 가장 가까운 물고기를 먹는다.

- (중요) 같은 거리에 먹을 수 있는 물고기가 많다면 가장 위에 물고기, 이 물고기도 많다면 가장 왼쪽의 물고기를 먹는다!

- 물고기를 먹으면 그 칸은 빈칸이 된다. 그리고 아기 상어는 해당 위치로 이동한다.

가장 처리하기 귀찮아 보이는 것은 바로 (중요)가 써있는 같은 거리에 먹을 수 있는 물고기가 많다면 가장 위에 물고기를 먹고, 이 물고기마저 많다면 왼쪽의 물고기를 먹는 것입니다.

다음 그림을 봅시다.

아기 상어를 기준으로 모든 물고기가 2초가 걸리는 위치에 있습니다!

(편의상 모든 물고기가 아기 상어보다 크기가 작다고 하겠습니다.)

우선, 가장 위에 있는 물고기를 먹기 때문에 아기 상어보다 두 칸 왼쪽에 있는 물고기는 먹지 않습니다.

그렇게 하더라도 위쪽에 물고기가 2개가 있습니다! 하지만, 조건에 따라서 왼쪽에 있는 물고기를 먹으므로, 결국 아기 상어는 노란색 물고기를 먹습니다.

그리고, 노란색 물고기가 있던 위치로 이동하죠.

그렇다면.. 이런 처리는 어떻게 하는것이 좋을까요?

바로! 우선순위 큐를 이용하는 것입니다.

물고기의 위치에 대한 구조체를 만들고, 물고기가 위에 있을 수록, 만약 같은 높이라면 왼쪽에 있을수록 우선 순위를 부여하는 것이죠.

struct COD {
    int r, c, cnt;
    COD(int r, int c) : cnt(0), r(r), c(c){}
    COD() : r(0), c(0), cnt(0) {}
};
 
struct cmp {
    bool operator()(COD c1, COD c2) {
        if (c1.r == c2.r) { return c1.c > c2.c; }
        return c1.r > c2.r;
    }
};
 
priority_queue<COD, vector<COD>, cmp> pq;

위 코드처럼 우선순위 큐의 사전 처리를 합시다!

이제 나머지 일은 BFS를 이용해서 가장 최단거리에 있는 물고기들의 정보를 우선순위 큐에 넣고, 

만약 먹을 수 있는 물고기가 있으면 우선순위 큐 가장 위에서 물고기를 잡아먹어 버리는 겁니다.

그리고 잡아먹은 물고기로 아기 상어가 이동한 후에 이동하는데 걸리는 시간을 결과값에 더해줍니다.

그리고 다시 다음에 잡아먹을 물고기를 찾는 작업을 반복합니다!

BFS가 힘드신 분들은 이곳을 먼저 봐주세요!

이제 이 과정을 그림으로 확인해 봅시다.

그림에는 안나왔지만, 2칸을 이동했기 때문에, 시간에는 2초를 더합니다.

먹이를 먹고 이동하는 풀 코드는 아래와 같습니다.

bool ff(FISH &f) {
    COD now = f.p;
 
    memset(visit, false, sizeof(visit));
    visit[now.r][now.c] = true;
    que.push(now);
 
    priority_queue<COD, vector<COD>, cmp> pq;
    queue<COD> temp;
    que = temp;
    que.push(now);
    int cnt;
    bool isfind = false;
 
    while (!isfind && que.size()) {
 
        cnt = que.size();
        while (cnt--) {
            now = que.front(); que.pop();
            if (mm[now.r][now.c] && mm[now.r][now.c] < f.size) {
                isfind = true;
                pq.push(now);
                continue;
            }
 
            for (int d = 0; d < 4; d++) {
                COD next = now;
                next.r += dr[d];
                next.c += dc[d];
                next.cnt++;
 
                if (isout(next.r, next.c)) continue;
                if (visit[next.r][next.c]) continue;
                if (mm[next.r][next.c] > f.size) continue;
                visit[next.r][next.c] = true;
                que.push(next);
            }
        }
        if (isfind) break;
    }
 
    if (isfind == false) return false;
 
    now = pq.top(); pq.pop();
    f.p = now;
    f.p.cnt = 0;
    f.eat();
    f.dist += now.cnt;
    mm[now.r][now.c] = 0;
    return true;
}

코드

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
 
int mm[20][20];
int n;
bool visit[20][20];
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
bool isout(int r, int c) { return r < 0 || c < 0 || r >= n || c >= n; }
 
struct COD {
    int r, c, cnt;
    COD(int r, int c) : cnt(0), r(r), c(c){}
    COD() : r(0), c(0), cnt(0) {}
};
 
struct cmp {
    bool operator()(COD c1, COD c2) {
        if (c1.r == c2.r) { return c1.c > c2.c; }
        return c1.r > c2.r;
    }
};
 
struct FISH {
    COD p;
    int remain;
    int dist;
    int size;
    FISH() :p({ 0,0 }), size(2), remain(2),dist(0) {}
 
    void eat() {
        remain--;
        if (remain == 0) { size++; remain = size; }
    }
};
 
queue<COD> que;
 
bool ff(FISH &f) {
    COD now = f.p;
 
    memset(visit, false, sizeof(visit));
    visit[now.r][now.c] = true;
    que.push(now);
 
    priority_queue<COD, vector<COD>, cmp> pq;
    queue<COD> temp;
    que = temp;
    que.push(now);
    int cnt;
    bool isfind = false;
 
    while (!isfind && que.size()) {
 
        cnt = que.size();
        while (cnt--) {
            now = que.front(); que.pop();
            if (mm[now.r][now.c] && mm[now.r][now.c] < f.size) {
                isfind = true;
                pq.push(now);
                continue;
            }
 
            for (int d = 0; d < 4; d++) {
                COD next = now;
                next.r += dr[d];
                next.c += dc[d];
                next.cnt++;
 
                if (isout(next.r, next.c)) continue;
                if (visit[next.r][next.c]) continue;
                if (mm[next.r][next.c] > f.size) continue;
                visit[next.r][next.c] = true;
                que.push(next);
            }
        }
        if (isfind) break;
    }
 
    if (isfind == false) return false;
 
    now = pq.top(); pq.pop();
    f.p = now;
    f.p.cnt = 0;
    f.eat();
    f.dist += now.cnt;
    mm[now.r][now.c] = 0;
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
 
    FISH f;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mm[i][j];
            if (mm[i][j] == 9) {
                f.p.r = i;
                f.p.c = j;
                mm[i][j] = 0;
            }
        }
    }
 
    while (ff(f)) {}
    cout << f.dist;
    return 0;
}
 
 

시간복잡도

우선 먹이를 찾는데 n*n 맵을 모두 탐색할 수 있습니다.

그리고 최대 n*n개의 물고기를 먹을 수 있기 때문에 시간복잡도는입니다.