[백준] 아기상어 - C++

백준-아기상어

문제 풀게된 계기

잠시 쉬는 타임에도 공부하려는 나의 의지

다만 내가 풀어본 BFS 문제 중 (몇안되지만..) 제일 어려웠당..
​

문제 해결 방법

최단거리를 구하는거라 BFS 사용

사실 이 문제가 어렵다고 느껴진 것은 조건이 너무 많아서..

문제 이해만 하는데 오래걸린 것 같다.

​

1. 현재 상어 위치에서 BFS를 시작해서 갈 수 잇는 거리 다 구하고 BFS 빠져나온다.
   BFS를 빠져나온 위치부터 다시 BFS를 실행 반복한다.

2. 현재 위치부터 상 하 좌 우에 인접한 거리로 상어가 이동할 수 있는 거리를 찾는다.
   찾은 거리 중에 상어의 크기(초기값 2)보다 작은 경우 vector에 담는다.
   방문한 흔적을 담기 위해 현재 위치의 방문에서 1을 더한 값을 넣어준다. (지금까지 상어가 이동한 횟수로 알 수 있으므로)
   인접한 거리가 없을 때 까지 맨 처음에 넣은 queue의 값을 제외한 queue의 사이즈만큼 반복문을 사용하여 발견
   (해당 상어 위치에서 갈 수 있는 방향의 최대 거리를 구할 수 있음)

3. 만약 vector에 담긴(상어가 먹을 수 있는 물고기들) 값들이 1이상인 경우에는 이 조건을 수행해야하므로 sort를 사용한다.
   (sort를 사용하면 가장 작은 값을 지닌 물고기를 먹으므로 가능 이 부분은 백준 질문검색 아이디어를 이용 ㅎㅎ 다들..천재..)

4. 가장 작은 값을 상어의 위치로 잡고 해당 위치의 visited(방문) 값을 result에 더해준다.

​

코드

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

#define MAX 21
using namespace std;

int N;
int sea[MAX][MAX];
int visited[MAX][MAX];
int sharkX, sharkY;
int sharkSize = 2;
int cnt = 0;
int result = 0;
bool ateCheck = false;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void BFS(){
    queue<pair<int, int>> q;
    vector<pair<int, int>> v;
    q.push(make_pair(sharkX, sharkY));
    visited[sharkX][sharkY] = 1;
    ateCheck = false;

    while(!q.empty()){
        int qSize = q.size();
        while(qSize--){
            int nx = q.front().first;
            int ny = q.front().second;

            q.pop();

            for (int i = 0; i < 4; ++i){
                int mx = nx + dir[i][0];
                int my = ny + dir[i][1];
                
                if (mx >= 0 && mx < N && my >= 0 && my < N && visited[mx][my] == 0){
                    
                    if (sea[mx][my] == 0 || sea[mx][my] == sharkSize){    // 상어 이동할 수 있는 범위
                        q.push(make_pair(mx, my));
                        visited[mx][my] = visited[nx][ny] + 1;
                    }                
                    else if (sea[mx][my] < sharkSize){   // 물고기 먹을 수 있을 경우
                        v.push_back(make_pair(mx, my));
                        visited[mx][my] = visited[nx][ny] + 1;
                    }
                }
            }
        }
        // 먹을 수 있는 상어가 여러마리 있을 경우 
        if (v.size() >= 1){   
            ateCheck = true;
            sort(v.begin(), v.end());
            sharkX = v[0].first;
            sharkY = v[0].second;
            sea[sharkX][sharkY] = 0;
            cnt++;
            result += visited[sharkX][sharkY] - 1;
            break;
        }   
    }
}

int main(void){
    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){
                sharkX = i; sharkY = j;
                sea[sharkX][sharkY] = 0;
            }
        }
    }

    while(1){
        BFS();
        memset(visited, 0, sizeof(visited));

        if (ateCheck == false) break;
        else if (cnt == sharkSize){ // 상어사이즈만큼 먹으면 1씩 상어크기는 자람 
            cnt = 0;
            sharkSize += 1;
        }
        
    }

    cout << result << endl;
}