[백준] 아기 상어

삼성 S직군 기출문제를 풀어 보았다. 중간에 너무 뻘짓만 안했다면 정말 재밌었던 문제 였고 내가 시나리오 + 도형 문제에 꽤 강점을 보인다는 자신감 또한 느꼈던거 같다. 일단 시나리오 자체를 설명하기에는 너무 어지럽게 상황이 많았다. 그래도 제일 중요하게 생각해야 하는 부분을 요약하자면,

1. 더 이상 먹을 물고기가 없을때 탐색을 끝낸다
2. 먹을 수 있는 물고기가 1마리면 바로 먹는다, 다만 먹을 수 있는 물고기가 1마리 이상이면
   • 가능성 있는 물고기중 가장 가까운 물고기를 먹는다
     • 가장 가까운 물고기 조차 하나 이상이라면,
       • 가장 위에 있는 물고기를 먹는다
         • 가장 위에 있는 물고기 조차 하나 이상이라면(여기서 부터 한숨 나온다) 가장 왼쪽에 있는 물고기를 먹는다

진짜 설명을 처음 들었을때 너무 어지러웠고 구현을 하는데 있어서도 어려움을 느꼈기에 노트에 글들을 정리하며 내 생각을 적은 결과 문제를 이해하고 코드를 작성할 수 있었다. 이게 바로 내가 생각하는 노트와 생각정리의 가장 큰 강점이 아닐까 싶다. 생각하는 방법을 기르는것.

정말로 내가 생각한데로 구현을 했고 거침없이 코드를 썼지만 내가 정말 뻘짓으로 생각했던 부분하나 때문에 힘듬을 겪었고 다시 고친 결과 깔끔한 코드가 나왔었다. 처음부터 적어보자면은,

난 원래 struct 같은 형태의 오브젝트를 사용하는것을 굉장히 싫어했지만, 이런 복잡한 도형 + 시뮬레이션 문제에서는 필수 라는것을 깨달았다.

Fish 벡터를 만든후에, 상어의 위치를 루핑하면서 찾아줬다 (사실 이 부분은 쓸데없긴 했다, 그냥 샤크 오브젝트를 매 조건마다 업데이트 해도 성공했을거다)

내가 제일 뻘짓했던 부분, 상어의 현재 위치에서 탐색을 해서 먹을 수 있는 물고기를 탐색 했어야 했는데 그냥 전체 벡터를 탐색하면서 먹을수 있는 물고기를 찾을려 했던게 정말 바보같은 선택이였다. 이렇게 하면은 당연히 조건에 맞게 해야하는 FishVec 의 크기도 커지는 건데 너무 실수했었다.

결국 고친 부분, bfs는 현재 상어의 위치에서부터 시작하자.

평범한 bfs 코드지만, 조건부만 보면, 빈칸이 아니고 먹을 수 있는 물고기 경우에는 물고기 벡터에 넣어주었다. visited를 활용해서 전부다 탐색 표시를 해주는것은 기본 중에 기본, 잊지말자!

이 다음부터는 조건부에 해당하는 대로 코드를 적어주었다

주석에 알맞는 설명이 적혀있다.

sort() 를 사용하는데 오브젝트 벡터는 다를까 싶었는데, 어떤 부분을 sort 하는지만 제시하면은 아무 문제없이 됐었다.

문제 설명에서 상어의 사이즈가 커지면은, 먹은 물고기도 초기화 된다는것을 언급했으면 좋았겠지만 자연스럽게 암시했던거 같다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N;
vector<vector<int>> matrix; 
bool visited[21][21]; 
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}}; 

struct Fish{
    int x, y, dist; 
};

struct Shark{
    int x, y, size; 
    int numAte = 0; 
};

void Input(){
    cin >> N; 
    vector<vector<int>> copy(N,vector<int>(N,0)); 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            int n; cin >> n;
            copy[i][j] = n;  
        }
    }
    matrix = copy; 
}

void bfs(Shark& shark, vector<Fish>& FishVec){
    queue<vector<int>> q; 
    q.push({shark.x, shark.y, 0}); 
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            vector<int> v = q.front();
            q.pop(); 

            int x = v[0], y = v[1], dist = v[2]; 

            visited[x][y] = true; 
            for(pair<int,int>& p: dir){
                int nX = x + p.first;
                int nY = y + p.second; 

                if(nX < 0 || nX >= N || nY < 0 || nY >= N || matrix[nX][nY] > shark.size || visited[nX][nY] == true) continue; 

                if(matrix[nX][nY] != 0 && matrix[nX][nY] < shark.size){
                    Fish fish; 
                    fish.x = nX; 
                    fish.y = nY; 
                    fish.dist = dist+1; 
                    FishVec.push_back(fish); 
                }

                visited[nX][nY] = true; 
                q.push({nX,nY,dist+1}); 
            }
        }
    }
}

void Solution(){
    int answer = 0; 
    Shark shark; 
    shark.size = 2; 

    vector<Fish> FishVec; 
    while(true){
        bool flag = false; 
        for(int i = 0; i < N; i++){ //상어의 위치 지정 
            for(int j = 0; j < N; j++){
                if(matrix[i][j] == 9){
                    shark.x = i; 
                    shark.y = j; 
                    flag = true; 
                    break; 
                }
            }
            if(flag) break; 
        }

        memset(visited,false,sizeof(visited)); //항상 visited 는 초기화 시켜준다  
        bfs(shark,FishVec); //전체 벡터에서 먹을 수 있는 물고기를 찾는게 아닌, 상어의 현재위치에서 먹을 수 있는 물고기들을 좌표에 넣어두자

        if(FishVec.empty()) break; //유일하게 끝나는 조건, 만약 더 이상 먹을 수 있는 물고기가 없을 경우 

        if(FishVec.size() == 1){ //먹을 수 있는 물고기가 계산해보니 단 한마리 일 경우, 
            answer += FishVec[0].dist; 
            matrix[FishVec[0].x][FishVec[0].y] = 9; //상어가 그쪽으로 이동한다
            matrix[shark.x][shark.y] = 0; //원래 상어 위치는 빈 공간으로 돌려놓는다 
        }

        else if(FishVec.size() > 1){
            int findMin = INT_MAX; 
            for(Fish& fish: FishVec){
                findMin = min(findMin,fish.dist); 
            }
            vector<Fish> tempFish; 
            for(Fish& fish : FishVec){
                if(fish.dist == findMin) tempFish.push_back(fish); 
            }

            if(tempFish.size() == 1){ //가장 가까운 물고기가 한마리 일 경우 
                answer += findMin; 
                matrix[tempFish[0].x][tempFish[0].y] = 9; //상어가 그쪽으로 간다 
                matrix[shark.x][shark.y] = 0; //원래 상어 위치는 빈 공간으로 돌려놓는다 
            }

            else if(tempFish.size() > 1){ //가장 가까운 거리에 물고기가 여러마리일 경우, 
                //가장 위에 있는 물고기를 먹어야 하고, 위에 있는 물고기 조차 여러마리면은 가장 왼쪽꺼를 먹는다 
                sort(tempFish.begin(), tempFish.end(), [](Fish& a, Fish& b){
                    if(a.x == b.x) return a.y < b.y; 
                    return a.x < b.x; 
                });
                answer += findMin; 
                matrix[tempFish[0].x][tempFish[0].y] = 9; //상어가 그쪽으로 간다 
                matrix[shark.x][shark.y] = 0; //원래 상어 위치는 빈 공간으로 돌려놓는다 
            }
        }



        //분명 이 과정을 거치면서 물고기 한마리 정도는 먹었을거다 
        shark.numAte++; 
        if(shark.numAte == shark.size){
            shark.size++; 
            shark.numAte = 0; 
        }
        FishVec.clear(); //Fish 리스트는 초기화 해준다.
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. Struct 적극 활용.
2. BFS 사용법.