[c++] BOJ 16236 :: 아기 상어

난이도 : 골드 4

걸린 시간 : ㅎㅎ.. 오래 걸림

 

문제

아기 상어 문제 바로가기

 

풀이

• bfs를 이용하여 먹을 수 있는 고기 찾기 + 상어로부터의 거리 찾기
• 거리가 가장 가까운 먹을 수 있는 고기들 찾기
• 그 중 가장 왼쪽 위에 있는 고기 찾기
• 상어가 해당 물고기의 위치로 이동해서 먹고, 먹은 물고기 개수가 size와 같아지면 size 키우기
• 상어보다 작은 물고기가 없을 때까지 반복

 

코드

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

using namespace std;

struct shark {
    int r; int c;
    int size = 2;
};

struct fish {
    int r; int c;
    int distance = 0;
    fish(int rp, int cp, int dist) {
        r = rp; c = cp; distance = dist;
    }
};

int N;
int map[21][21];
int mapDist[21][21];
int direction[4][2] = { {0,-1}, {-1,0}, {1, 0}, {0,1} };
shark baby;

/* 먹을 수 있는 고기들을 따로 찾으면 실패함!
vector<pair<int, int>> findFish() {
    // 먹을 수 있는 고기들의 위치 return
    vector<pair<int, int>> res;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] != 0 && map[i][j] < baby.size) {
                res.push_back(make_pair(i, j));
            }
        }
    }
    return res;
}
*/

vector<pair<int, int>> bfs() {
    // 아기상어에서 모든 점까지의 최소 거리 찾기
    fill(&mapDist[0][0], &mapDist[20][20], 1e9);
    queue<pair<int, int>> que;
    que.push(make_pair(baby.r, baby.c));
    mapDist[baby.r][baby.c] = 0;
    vector<pair<int, int>> fishes;

    while (!que.empty()) {
        pair<int, int> pos = que.front(); que.pop();
        int row = pos.first; int col = pos.second;
        for (int i = 0; i < 4; i++) {
            int rtemp = row + direction[i][0];
            int ctemp = col + direction[i][1];
            if (rtemp < 0 || ctemp < 0 || rtemp >= N || ctemp >= N) // 맵 밖이면
                continue;
            if (mapDist[rtemp][ctemp] != 1e9) // 이미 들렀던 곳이면
                continue;
            if (map[rtemp][ctemp] == baby.size || map[rtemp][ctemp] == 0) { // size가 같거나 0이면 fishes에 넣지 x
                mapDist[rtemp][ctemp] = (mapDist[row][col] + 1);
                que.push(make_pair(rtemp, ctemp));
            }
            else if (map[rtemp][ctemp] < baby.size) {
                fishes.push_back(make_pair(rtemp, ctemp));
                mapDist[rtemp][ctemp] = (mapDist[row][col] + 1);
                que.push(make_pair(rtemp, ctemp));
            }
        }
    }
    return fishes;
}

fish* findSmallest(vector<pair<int, int>>& fishes) {
    // 가장 거리가 짧은 고기들 찾기
    vector<pair<int, int>> mini;
    int min = 1e9;
    for (int i = 0; i < fishes.size(); i++) {
        pair<int, int> fish = fishes[i];
        if (min > mapDist[fish.first][fish.second]) { // min 갱신
            min = mapDist[fish.first][fish.second];
            mini.clear();
            mini.push_back(make_pair(fish.first, fish.second));
        }
        else if (min == mapDist[fish.first][fish.second]) {
            mini.push_back(make_pair(fish.first, fish.second));
        }
    }

    // 왼쪽 위 고기 채택
    fish* f = new fish(mini[0].first, mini[0].second, min);
    for (int i = 1; i < mini.size(); i++) {
        if (mini[i].first < f->r) {
            // 더 위에 있으면
            f->r = mini[i].first;
            f->c = mini[i].second;
        }
        else if (mini[i].first == f->r && mini[i].second < f->c) {
            // row는 같은데 왼쪽에 있으면
            f->r = mini[i].first;
            f->c = mini[i].second;
        }
    }

    return f;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) {
                baby.r = i;// 상어 저장
                baby.c = j;
                map[i][j] = 0; // 맵에서 상어 지우기
            }
        }
    }

    int move = 0;
    int eat = 0;

    while (1) {
        vector<pair<int, int>> fishes = bfs(); // 먹을 수 있는 고기 찾기 + 거리 표시
        if (fishes.empty())
            break;
        fish* f = findSmallest(fishes); // 거리가 가장 가까우면서 왼쪽 위에 있는 고기 찾기

        move += f->distance; // 이동 거리 더해주기
        baby.r = f->r; baby.c = f->c; // 상어 이동
        map[baby.r][baby.c] = 0; // 먹은 물고기는 map에서 0으로 만들기
        eat++;

        if (eat == baby.size) { // 크기만큼 물고기를 먹으면 크기가 1 커짐
            baby.size++;
            eat = 0;
        }
    }
    cout << move << '\n';
}

 

주의할 점

bfs에서 바로 상어와의 크기를 비교해서 먹을 수 있는 고기들을 고르는 것과, 따로 map을 돌면서 미리 먹을 수 있는 고기들을 골라두는 것이 차이가 있나보다. 후자의 방법을 처음 택하였고 실패합니다가 떠서 전자의 방법으로 풀게 되었다.

후자의 방법도 반례를 모두 통과하는 게 함정..

 

결과