[ baekjoon ] #16236 아기 상어

백준 #16236 아기 상어

문제 요약

---

• NxN 크기의 공간에 물고기 M마리, 아기 상어 1마리 존재
• 한 칸에는 최대 1마리 존재
• 가장 처음 아기 상어의 크기는 2, 1초에 상하좌우로 인접한 한 칸씩 이동
• 아기 상어는 자신보다 큰 물고기가 있는 칸은 지나갈 수 없음
• 크기가 같은 물고기는 먹을 수 없지만 이동은 가능
• 아기 상어 이동 규칙
  - 더 이상 먹을 수 있는 물고기가 없다면 엄마 상어에게 도움 요청
  - 먹을 수 있는 물고기가 1마리면 먹음
  - 먹을 수 있는 물고기 ＞ 1인 경우 가장 가까운 물고기 먹음
  • 거리는 아기 상어 → 물고기 칸으로 이동할 때 지나야하는 칸 개수의 최솟값
  • 거리가 가까운 물고기가 많을 경우 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기를 먹음
• 아기 상어의 이동은 1초 걸리고 먹는 데 걸리는 시간 X
  → 이동과 동시에 물고기 먹음 → 빈 칸이 됨
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기 1 증가
• 아기 상어가 도움 요청하지 않고 물고기를 잡아먹을 수 있는 시간 구하기 !

💡Idea

1. 아기 상어를 어디로 이동시킬지 어떻게 결정할까?
   • 아기 상어 위치에서 갈 수 있는 곳을 다 가보면서 거리를 구하자 !
     → 이때 0이거나 아기 상어와 크기가 같다면 물고기를 먹을 수는 없다.
   • 아기 상어보다 작고 0이 아닐 경우 즉, 먹을 수 있는 물고기가 있을 경우 제일 짧은 거리를 저장
2. 아기 상어가 갈 수 있는 곳 중에서 조건을 만족하는 위치를 어떻게 찾을까?
   • 2중 for문을 이용해서 제일 먼저 찾는 곳을 다음 아기 상어 위치로 변경해준다 !
     → 이때 잡아 먹은 물고기 개수를 증가시키고 아기 상어 크기와 같다면 크기 증가시키기

[ SourceCode ]

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

int N, time_cnt = 0; // 공간의 크기 (NxN), 시간
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
int visit[21][21];
pair <int, int> baby(2, 0); // 아기 상어 처음 크기 2, 잡아먹은 물고기 0
pair <int, int> next_locate;

bool find_fish(vector <vector<int>> &shark) {
    fill(&visit[0][0], &visit[21][0], 400); // 초기화
    int dist = 400;
    bool flag = false;
    queue <pair<int, int>> list;
    int x = next_locate.first;
    int y = next_locate.second;
    visit[x][y] = 0;
    list.push({x, y});

    // 아기 상어가 갈 수 있는 곳 탐색하기
    while(!list.empty()) {
        int cx = list.front().first;
        int cy = list.front().second;
        list.pop();

        for(int i=0; i<4; i++) {
            int nx = cx + dir[i][0];
            int ny = cy + dir[i][1];

            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(shark[nx][ny] > baby.first) continue;
            if(visit[nx][ny] == 400) {
                list.push({nx, ny});
                visit[nx][ny] = visit[cx][cy] + 1;
            }
            // 먹을 수 있는 경우에만 dist 갱신
            if(shark[nx][ny] != 0 && shark[nx][ny] < baby.first) {
                flag = true;
                dist = min(dist, visit[nx][ny]);
            }
        }
    }

    if(!flag) return false;
    else {
        bool check = false;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(shark[i][j] == baby.first || shark[i][j] == 0) continue;
                if(dist == visit[i][j]) {
                    shark[next_locate.first][next_locate.second] = 0;
                    next_locate = {i, j};
                    baby.second++;
                    if(baby.first == baby.second) {
                        baby.first++;
                        baby.second = 0;
                    }
                    shark[i][j] = 0;
                    time_cnt += dist;
                    check = true;
                    break;
                }
            }
            if(check) break;
        }
    }

    return true;
}

int main() {
    // 1. 입력 받기
    cin >> N;
    vector <vector<int>> shark(N, vector<int>(N));
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> shark[i][j];
            if(shark[i][j] == 9) {
                next_locate = {i, j};
            }
        }
    }

    // 2. 아기 상어 이동하기
    while(1) {
        bool check = find_fish(shark);
        if(!check) break;
    }

    cout << time_cnt;

    return 0;
}

Feedback

---

1. 아기 상어가 이동한 곳의 값을 바꿔주지 않아서 시간을 오래 썼다,,