백준 16236 아기 상어 c++ [컴공과고씨]

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

16236번: 아기 상어

 

문제 간단 정리.

상어가 물고기를 먹으러 다님.

상어는 물고기의 크기보다 크면 물고기를 먹을 수 있음.

크기가 같다면 지나갈 수만 있음. -> 작으면 못지나 감.

물고기를 먹으면 그 칸은 빈칸이 됨.

상어가 한 크기에서 물고기를 먹은 횟수와 상어의 크기가 같게 되면 상어 크기가 1 증가함.

물고기를 먹을 때는 가장 작은 것을 우선으로 먹고 같은 크기가 많다면 가장 위쪽 우선 그 다음은 왼쪽 우선으로 함.

한 칸 움직일 때마다 1초가 지나고 먹을 수 있는 물고기칸에 도착하면 그 즉시 먹음.

이 때 먹을 물고기가 없을 때 까지의 걸리는 시간을 구해라.

 

문제 해결 방법

문제를 읽었을 때 bfs 탐색 문제라는 것을 쉽게 알 수 있습니다.

조건을 잘 지켜주어야 합니다.

저는 물고기를 한 마리 먹을 때까지 bfs로 탐색 후 먹으면 조건들에 구현해 주었고 다시 bfs를 넣어서 또 한마리를 먹을때 까지 탐색하는 방법으로 구현했습니다.

bfs 내부 같은 경우 일반적인 bfs 구현과 비슷하지만 먹을 물고기를 찾았을 때 그 위치를 저장하고 다른 같은 크기의 같은 시간이 걸리는 물고기 중에서 가장 위쪽, 왼쪽에 있는 좌표가 있다면 그 좌표에 있는 물고기를 먹도록 구현해 주었습니다.

자세한 것은 전체 코드의 주석을 보면 이해가 더욱더 쉬울 것입니다.

중요한 것은 가장 위쪽, 왼쪽을 우선시 한다는 것을 잘 지켜주는 것이 중요합니다. 

 

전체코드

#include <iostream>
#include <queue>
 
using namespace std;
int n;
int map[22][22];
int dx[] = {0, -1, 1, 0}; // 상좌우하
int dy[] = {-1, 0, 0, 1};
int bx, by;
int result = 0; // 총 걸린 시간
int count = 0; // 물고기 먹은 횟수
int sz = 2; // 상어 사이즈
bool stop = false; // 먹을 물고기가 없는 경우
bool eat = false; // 한 마리를 먹은 경우
void bfs(int a, int b, bool visit[][22], int shSize){
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(a, b), 0));
    visit[b][a] = true;
    int temp; // 한 마리를 먹는데 걸린 시간
    while(!q.empty()){
        int x = q.front().first.first; // 열 좌표
        int y = q.front().first.second; // 행 좌표
        int cnt = q.front().second; // 현재 시간
        // 가장 위쪽을 먼저 그 다음 왼쪽을 우선적으로 먹는 것을 고려
        if(map[y][x] > 0 && map[y][x] <shSize && temp == cnt){
            if((by > y) || (by == y && bx > x)){
                by = y; // 물고기를 먹은 상어 위치 저장
                bx = x;
                continue;
            }
        }
        q.pop();
        for (int i = 0; i < 4; i++){
            int nx = x + dx[i]; // 방향 이동
            int ny = y + dy[i];
 
            if(nx>=0 && nx <n && ny>=0 && ny <n && !visit[ny][nx]){
                if(map[ny][nx] <= shSize){// 지나가거나 먹을 수 있는 경우
                    if(map[ny][nx] > 0 && map[ny][nx] < shSize && !eat){ //물고기를 먹을 수 있는 경우
                        eat = true; // 한 마리 먹음
                        bx = nx; //시작 위치를 물고기를 먹었던 위치로
                        by = ny;
                        temp = cnt + 1; // 한 마리 먹는데걸린 시간
                        result += temp; // 총 시간에 추가
                    }else{ // 물고기를 못먹는 경우
                        q.push(make_pair(make_pair(nx, ny), cnt + 1));
                        visit[ny][nx] = true;  
                    }                      
                }
            }
        }
    }
}
int main(){
    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){
                by = i; // 상어 시작 위치
                bx = j;
                map[i][j] = 0;
            }
        }
    }
 
    while(!stop){
        bool visit[22][22] = {0};
        bfs(bx, by, visit, sz); // 한 마리 먹을때까지 이동
        if(eat){ // 먹었을 경우
            eat = false; 
            count += 1; // 현재 크기에서 물고기 먹은 횟수 증가
            map[by][bx] = 0; // 먹은 물고기 삭제
            if(count == sz){ // 상어 크기가 증가하는 경우
                sz += 1; // 상어 사이즈 +1
                count = 0; //현재 크기에서 물고기 먹은 횟수 초기화
            }
        }else{ // 한 마리도 못먹는 경우
            stop = true; // 엄마 상어에게 도움 요청해야함.
        }
    }
    cout << result << '\n';
    return 0;
}