백준 16236번: 아기 상어

문제 링크 : https://www.acmicpc.net/problem/16236

참고 사이트 : https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4

물고기를 먹는 조건
1. 가장 가까이에 있는 먹을 수 있는 물고기부터 먹는다. -> 최단 거리
2. 걸리는 시간이 똑같다면, 가장 위에 있는 물고기부터 먹는다.
3. 같은 행에 있다면 가장 왼쪽에 있는 물고기부터 먹는다.

아기 상어의 이동 조건
1. 물고기 크기 > 아기 상어 크기 -> 이동 X
2. 물고기 크기 == 아기 상어 크기 -> 이동 O
3. 물고기 크기 < 아기 상어 크기 -> 이동 O, 먹을 수 있음

위 두 조건을 체크하면서 bfs를 진행하면 됐다. 근데 일반적인 bfs랑은 조금 달랐다. 가장 위, 가장 왼쪽부터 먹는다는 조건을 bfs 탐색 순서에서 반시계 방향으로 위, 왼쪽, 아래, 오른쪽으로 지정을 하면 맞게 탐색이 될 줄 알았다. 근데 테케는 정답이 나오고, 어떤 테케는 값이 +-2 정도의 오차가 발생했다.

bfs 탐색 순서가 아니라, if문으로 직접 더 위에 있는지, 더 왼쪽에 있는지를 따로 체크를 해 주어야 하는 것이었다. 참고한 velog 글에서 이 부분을 따로 구현해야 한다는 부분만 보고 코드는 직접 짰다! 뿌듯하구만

• 구현 순서

1. 현재 상어의 위치에서 bfs로 갈 수 있는 모든 곳 방문, 그 중에서 물고기를 먹는 조건에 맞는 (최소 시간, 가장 위, 가장 왼쪽) 한 좌표를 구함.
2. 해당 점으로 이동해서 물고기를 먹음 -> 좌표 값 변경
   2-1. 아기 상어의 사이즈만큼 먹었으면 크기 증가
   2-2. 전체 걸린 시간 증가시켜줌
3. 도착 좌표를 출발 좌표로 해서 다시 1번 진행
   3-1. 탐색이 끝났을 때, 도착 좌표가 출발 좌표와 같다면 종료 (이동 X이므로)
   
   

<작성한 코드>

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

int n, num, ans, sharkSize = 2; // num = 현재까지 먹은 물고기 수 -> 사이즈 같아지면 0으로
int sea[21][21], visited[21][21];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
queue<pair<int, int>> q;

void init(){
    for(int i = 0; i < n; i++)
        memset(visited[i], 0, sizeof(int) * n);
}

void bfs(pair<int, int> s){
    int sec = 99999; // 최소 걸린 시간
    int minX = s.first, minY = s.second;
    q.push(s);
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second; // 현재 아기 상어 위치 x y 좌표
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i]; // 인접한 4방향 이동하면서 체크
            
            if(0 <= nx && nx < n &&
            0 <= ny && ny < n &&
            visited[nx][ny] == 0 &&
            sea[nx][ny] <= sharkSize){ // 범위 안의 값, 아직 가지 않은 곳
                if(sea[nx][ny] != 0 && sea[nx][ny] < sharkSize){ // 작은 물고기가 있는 경우 먹는 후보
                    if(visited[x][y] < sec){ // 현재 온 곳이 최소 시간인 경우
                        sec = visited[x][y];
                        minX = nx, minY = ny;
                    }
                    else if(visited[x][y] == sec){ // 같은 시간 걸리는 경우 가장 위, 가장 왼쪽
                        if(nx < minX){
                            minX = nx, minY = ny;
                        }
                        else if(x == minX){
                            if(y < minY)
                                minX = nx, minY = ny;
                        }
                    }
                }
                visited[nx][ny] = visited[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    pair<int, int> go = {minX, minY};
    if(s == go){ // 이동 x -> 종료
        cout << ans;
        exit(0);
    }
    
    sea[minX][minY] = 0;
    num++; // 이동 후 먹음
    if(num == sharkSize){
        num = 0;
        sharkSize++;
    }
    
    ans += sec + 1;
    init();
    bfs(go);
}

int main(){
    pair<int, int> s;
    
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            cin >> sea[i][j];
            if(sea[i][j] == 9){
                s = {i, j};
                sea[i][j] = 0;
            }
        }
    
    bfs(s);
}