[백준/C++] 16236번 아기상어

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

16236번: 아기 상어

1. 입력받을 때, 9가 나오면 상어의 위치이므로 기록해둔다.

2. 다른 물고기들의 개수를 세서 물고기가 오직 한마리면 바로 거리를 계산하고 종료!

-> (x좌표의 차 + y좌표의 차) = 거리

3. 만약 물고기가 여러 마리일 경우, bfs()를 반복실행!​

※ 반복실행하는 이유 : 상어가 가장 가까운 먹이를 찾아서 그것을 먹을 때 마다, 다른 먹이들과의 최단거리가 바뀌기 때문에 다시 게산해주어야 하므로!

4. bfs() 안에서는, 다음 탐색할 곳이 범위 안이고 아직 방문하지 않았으며 상어의 크기보다 작거나 같을 경우에만 탐색하여 상어로부터의 거리를 계산해준다.

5. 만약 가까운 물고기가 여러 마리일 경우에는 가장 위 + 가장 왼쪽부터 먹는다고 하였으므로, 맵의 좌상단부터 for문을 돌려주면 된다!

-> for문이 끝나면 현재 상어위치에서부터 가장 가까운 먹이의 좌표와 그 먹이까지의 거리를 알 수 있게 된다.

6. 만약 거리가 갱신되지 않았다면, 알맞은 먹이를 찾지못하였기에 이제 엄마의 도움을 요청해야함 = 탐색 종료

7. 갱신되었다면

• 현재 상어가 있는 곳은 빈칸으로 바꿔주기
• 섭취한 먹이가 있던 곳을 상어가 있는 곳으로 바꿔주기
• 섭취한 먹이까지의 거리를 정답 변수에 더해주기
• 경험치를 1 증가시켜 경험치가 상어의 크기와 같아진다면, 레벨업이므로 경험치를 초기화시켜주고 상어의 크기 + 1 한 뒤

true를 반환하여 다시금 탐색을 이어나가면 된다!

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>

using namespace std;

int n,level=2,exp,cnt,sec,ans;
int a,b,c,d;
int map[21][21];
int dist[21][21];
queue<pair<int,int>> q;
bool visited[21][21];

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

bool bfs(){

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(ny>=0 && ny<n && nx>=0 && nx<n && dist[nx][ny]==-1 &&map[nx][ny]<= level ){
                dist[nx][ny] = dist[x][y]+1;
                q.push({nx, ny});
            }
        }
    }
    int mx = 0;
    int my = 0;
    int m_dist = 987654321;
    for(int i=n-1; i>=0; i--){
        for(int j=n-1; j>=0; j--){
            if(map[i][j]!=0 && map[i][j] !=9&& map[i][j]<level && dist[i][j] != -1 && dist[i][j]<=m_dist){
                m_dist = dist[i][j];
                mx = i;
                my = j;
            }
        }
    }
    if(m_dist == 987654321){
        return false;
    }else{
        map[a][b] =0;
        a = mx;
        b = my;
        exp++;
        if(level == exp){
            exp=0;
            level++;
        }
        map[mx][my] = 9;
        ans+= dist[mx][my];
        return true;
    }
}

void go(int a, int b, int c, int d){
    int sx = abs(a-c);
    int sy = abs(b-d);

    cout << sx + sy;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    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) {
                a=i;
                b=j;
            }
            else if(map[i][j] >=1 && map[i][j] <=6){
                cnt++;
                if(cnt==1){
                    c=i+1; d=j+1;
                }
            }
        }
    }
    if(cnt==1) go(a+1,b+1,c,d);
    else {
        while (true) {
            memset(dist, -1, sizeof(dist));
            dist[a][b] = 0;
            q.push({a, b});
            if (bfs()) {
                continue;
            } else break;
        }
        cout << ans;
    }
    return 0;
}