[BOJ] 16236. 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

처음에 입력받을 때 아기 상어의 위치에 값이 9가 들어가 있는데, 아기 상어의 좌표를 큐에 넣어줬으면 값을 다시 0으로 바꿔주는 것이 좋다.

아기 상어의 원래 위치를 몸집이 9인 물고기로 생각하고 이동을 못할 수도 있기 때문이다.

물론 이렇게 안 해주고 이동할 때 0에서 6으로 정확히 조건을 처리해줘도 상관없다.

 

문제에 나와있는 다음과 같은 조건에 따라 아기 상어를 이동시키며 물고기를 잡아먹으면 된다.

 

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

아기 상어의 이동은 bfs를 이용하고 가장 가까운 거리에서 먹을 수 있는 물고기들을 비교하기 위해서는 큐사이즈 만큼(같은 거리)만 먼저 진행하여 단계별로 진행하도록 하였다. 같은 단계 안에서 먹을 수 있는 물고기들이 있다면 더 위쪽에 있고 더 왼쪽에 있는 물고기의 위치를 저장해 놓는다. 즉, x좌표가 더 작고 그다음으로 y좌표가 더 작은 경우이므로 잡아먹을 물고기의 좌표를 초기값으로 큰 값을 넣어둔 후 물고기의 위치가 더 작은 값이라면 변경해준다.

 

 

현재 단계의 탐색이 끝났다면 잡아 먹을 물고기가 있었는지 확인한다. 잡아 먹을 물고기의 좌표가 변해있다면 있는 것이다. 그러면 잡아먹을 물고기의 좌표로 이동 후에 바로 잡아먹는다. 문제 조건에 따라먹을 때마다 먹은 수를 증가시키고 아기 상어의 크기와 비교해주어야 한다.

 

 

잡아먹은 후에는 큐를 비워준 후 큐에 아기 상어의 위치를 새로 넣어주고 다시 탐색을 시작하면 된다. 이때 방문을 체크하는 배열도 같이 초기화해주어야 한다.

 

더 자세한 설명은 코드 참고!

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int n,shark, ans;
int map[20][20];
int visit[20][20];
 
int dx[] = {0,0,1,-1};
int dy[] = { 1,-1,0,0 };
 
queue<pair<int, int>> q;
 
void solve() {
 
 
    int x, y;
 
    //잡아먹을 물고기의 좌표
    int movex = 100, movey = 100;
 
    //먹은 물고기 수
    int eatcnt = 0;
 
    while (!q.empty()) {
        int qsize = q.size();
 
        //큐의 사이즈만큼만 진행하면서 단계별로(시간별로) 진행할 수 있다.
        while (qsize-- > 0) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
 
                //범위 체크
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                //방문 체크
                if (visit[nx][ny]) continue;
                //아기상어보다 크기가 크면 못지나간다.
                if (map[nx][ny] > shark) continue;
 
                //이동할 곳을 큐에 넣고 시간을 체크
                q.push(make_pair(nx, ny));
                visit[nx][ny] = visit[x][y] + 1;
 
                //먹을 수 있는 물고기가 있다. (크기가 아기상어보다 작고 빈칸은 아니다)
                if (map[nx][ny] != 0 && map[nx][ny] < shark) {
                    //먹을 수 있는 물고기중 더 위쪽의 물고기를 먹는다.
                    if (movex > nx) {
                        movex = nx;
                        movey = ny;
                    }
                    else if (movex == nx) { //똑같이 위쪽에 있다면 더 왼쪽에 있는 물고기를 먹는다.
                        if (movey > ny) {
                            movex = nx;
                            movey = ny;
                        }
                    }
                }
            }
        }
 
 
        //먹은 물고기가 있다. (먹을 물고기의 좌표가 초기값이 아니다)
        if (movex != 100) {
 
            //먹은 물고기수 증가
            eatcnt++;
 
            //먹은 물고기 수가 아기상어의 크기와 같아졌다면 아기상어의 크기 증가, 먹은 물고기 수는 초기화
            if (eatcnt == shark) {
                shark++;
                eatcnt = 0;
            }
 
            //잡아먹으므로 값 0으로 바꿔줌
            map[movex][movey] = 0;
 
            //현재 위치까지의 시간을 따로 저장해놓는다.
            int time = visit[movex][movey];
 
            //현재 위치에서 새로 탐색을 시작하기 위해서 기존의 큐는 모두 비워준다.
            while (!q.empty()) q.pop();
            //시간을 체크한 visist배열도 초기화
            memset(visit, 0, sizeof(visit));
 
 
            //아기상어의 새로운 위치를 새로 큐에 추가하고 아까 저장해놓은 시간을 visit배열에 저장
            q.push(make_pair(movex, movey));
            visit[movex][movey] = time;
 
            //마지막으로 물고기를 먹었을 때의 시간을 저장
            ans = time;
 
            //먹을 물고기 위치 초기화
            movex = 100;
            movey = 100;
        }
 
    }
    
 
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
 
            //아기상어인 경우 큐에 추가 및 시간 0으로 표시
            if (map[i][j] == 9) {
                q.push(make_pair(i, j));
                visit[i][j] = 0;
 
                //나중에 아기상어가 다시 지나갈 수 있도록 0으로 바꿔준다.
                map[i][j] = 0;
            }
        }
    }
 
    //상어 초기 크기
    shark = 2;
    solve();
    
 
    cout << ans << '\n';
    return 0;
}