[BOJ][삼성기출] 16236. 아기 상어

문제 접근

1. 먹을 수 있는 물고기 탐색이 포인트이다. (get_target())
   • 우선 모든 물고기에 대해 상어와의 거리를 구한다.
   • 그 다음 먹을 수 있는 물고기가 있다면 물고기의 정보를 반환한다.

     우선 모든 물고기의 거리를 -1로 세팅한다.
     bfs를 통해 도달 가능한 물고기의 거리를 update한다.
     만일, update 후에도 모든 물고기의 상어와의 거리가 -1이면 먹을 수 있는 물고기가 없는 것이므로 -1을 반환한다. (먹을 수 있는 물고기가 있는지 여부 탐색 방법)
     거리가 -1이 아닌 물고기가 한 마리 이상 있다면 거리가 최소 거리에 위치한 물고기를 먹는다.
     최소 거리에 위치한 물고기가 여러 마리라면, vector에서 가장 첫 번째로 탐색되는 물고기가 문제에서 정의하는 우선순위에 부합하게 된다. (입력 시 차례대로 vector에 넣었으며, 입력은 왼쪽 위부터 시작됐기 때문이다.)

2. 다른 사람들의 풀이를 보니 food 구조체에 life 변수를 쓰지 않았다. (과거의 나 또한)
   그래도 문제를 풀 때 내가 세운 논리는 정리되었다.
   다음에 리뷰를 해보면 좋을 것 같다.
   

풀이

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct food {
    int x;
    int y;
    int size;
    int d;
    bool life;
} food;

int N, M, rst, cnt, sx, sy, s_size;
int map[20][20];
vector <food> F;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            if (map[i][j] > 0 && map[i][j] < 9) {
                food f;
                f.x = i; f.y = j; f.size = map[i][j]; f.d = 0; f.life = true;
                F.push_back(f);
            }
            else if (map[i][j] == 9) {
                sx = i; sy = j; s_size = 2;
            }
        }
    }
    rst = 0; cnt = 0;
}

void get_target(int ret) {
    rst += F[ret].d;
    map[sx][sy] = 0;
    sx = F[ret].x;
    sy = F[ret].y;
    F[ret].life = false;
    map[F[ret].x][F[ret].y] = 9;

    cnt++;
    if (s_size == cnt) {
        s_size++;
        cnt = 0;
    }
}

int is_range(int x, int y) {
    if (x >= 0 && x < N && y >= 0 && y < N) return true;
    return false;
}

int find_target() {
    int is_visit[20][20];
    memset(is_visit, 0, sizeof(is_visit));
    queue <pair<pair<int, int>, int>> Q;
    
    Q.push(make_pair(make_pair(sx, sy), 0));
    is_visit[sx][sy] = 1;

    for (int i = 0; i < F.size(); i++) {
        F[i].d = -1;
    }
    // 1. 모든 먹을 수 있는 물고기에 대해 상어와의 거리를 구한다.
    while (!Q.empty()) {
        int cx = Q.front().first.first;
        int cy = Q.front().first.second;
        int d = Q.front().second;
        Q.pop();
        // 현재 위치에 물고기가 있는지 확인
        for (int i = 0; i < F.size(); i++) {
            if (map[cx][cy] && cx == F[i].x && cy == F[i].y) {
                if (map[cx][cy] < s_size) {
                    F[i].d = d;
                    break;
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (!is_visit[nx][ny] && is_range(nx, ny) && map[nx][ny] <= s_size) {
                is_visit[nx][ny] = 1;
                Q.push(make_pair(make_pair(nx, ny), d + 1));
            }
        }
    }

    // 2. 살아 있는 물고기 중 먹을 수 있는 물고기가 한 마리 이상 있는가?
    bool flag = false;
    for (int i = 0; i < F.size(); i++) {
        if (F[i].life && F[i].d != -1) flag = true;
    }
    if (!flag) return -1; // 없다면 종료

    //있다면 min distance를 구하고 min distance에 해당하는 물고기 중 가장 왼쪽에 위치한 물고기
    int m = 100000;
    for (int i = 0; i < F.size(); i++) {
        if (F[i].life && F[i].d != -1) m = min(m, F[i].d);
    }

    for (int i = 0; i < F.size(); i++) {
        if (F[i].life && F[i].d != -1) {
            if (F[i].d == m) return i;
        }
    }
}

void solve() {
    while(true) {
        int ret = find_target();
        if (ret == -1) {
            break;
        }
        get_target(ret);
    }
}

int main() {
    input();
    solve();
    cout << rst << endl;
}