백준 16236 - 아기 상어 - BFS

문제

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

풀이전략

1. 문제를 잘 읽어보면 자기 보다 큰 물고기는 못지나가고, 작은 물고기는 잡아먹지만, 크기가 같은 물고기는 그냥 이동은 가능하다.
2. 가까운 물고기가 많다면 가장 위 & 가장 왼쪽을 우선적으로 먹는다.
3. 스트럭쳐를 만들어서 해결하고, 물고기를 찾을 때마다 BFS를 해야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int mp[22][22];
bool ch[22][22];
int dy[4] = {-1, 0, 0, 1};
// dx를 실수
int dx[4] = {0, -1, 1, 0};
// fish는 shark에 대한 위치와 값을 저장하기 위함이다. 
struct fish{
    int r, c, val;
    fish(int aa, int bb, int cc){
        r = aa;
        c = bb;
        val = cc;
    }
    // 상어들중 우리가 선택해야하는 경우는 가장 위에 가장 왼쪽에 위치한 상어이다.
    bool operator<(const fish& f) const{
        if(r == f.r) return c < f.c;
        return r < f.r;
    }
};

// 상어가 새로운 먹이를 찾아 나서는 부분이다. 
fish BFS(int r, int c, int shark){
	// ans라는 벡터에 먹을 수 있는 물고기들의 후보들을 넣는다. 
    vector<fish> ans;
    queue<fish> q;
    q.push(fish(r, c, 0));
    mp[r][c] = 0;

    int distance = 0;

    while(!q.empty()){
        fish ret = q.front();
        ch[ret.r][ret.c] = true;
        q.pop();
        if(distance != 0 && ret.val >= distance ) continue;
        for(int i=0; i<4; i++){
            int rr = ret.r + dy[i];
            int cc = ret.c + dx[i];

            if(!ch[rr][cc] && mp[rr][cc]<=shark && rr > 0 && rr<=N && cc>0 && cc<=N){

                if(mp[rr][cc] < shark && mp[rr][cc] != 0){
                    
                    if(distance == 0){
                        distance = ret.val+1;
                    }   
                    ans.push_back(fish(rr, cc, ret.val+1));
                    ch[rr][cc] = true;
                }
                else{
                    
                    ch[rr][cc] = true;
                    q.push(fish(rr,cc,ret.val+1));
                }
            }
        }
       
    }
    sort(ans.begin(), ans.end());
    if(ans.empty()) return fish(0,0, -1);
    return ans[0];
        // fish res = ans[0];
        // ans.clear();
        // return res;
}

int getShark(int r, int c){

    int shark = 2;
    int sharkCount = 0;
    int res = 0;
    int rr = r, cc = c;
    while(1){
        memset(ch, false, sizeof(ch));
        mp[rr][cc] = 0;
        ch[rr][cc] = true;
        fish s = BFS(rr,cc, shark);
        
        if(s.val == -1) return res;
        res += s.val;
        sharkCount++;
        if(sharkCount == shark){
            sharkCount = 0;
            shark++;
        }
        rr = s.r;
        cc = s.c;
        
    }
    
    return res;
}


int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int R, C;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            cin >> mp[i][j];
            if(mp[i][j] == 9){
                R = i;
                C = j;
            }
        }
    }
    
    cout<<getShark(R,C)<<endl;

    return 0;
}


// int BFS(int r, int c){

//     queue<fish> q;
//     queue<fish> ans;
//     q.push(fish(r, c, 0));
//     mp[r][c] = 0;

//     int shark = 2;
//     int sharkCount = 0;
//     int res = 0;
    
//     while(!q.empty()){
//         fish ret = q.front();
//         ch[ret.r][ret.c] = true;
//         q.pop();
//         for(int i=0; i<4; i++){
//             int rr = ret.r + dy[i];
//             int cc = ret.c + dx[i];

//             if(!ch[rr][cc] && mp[rr][cc]<=shark && rr > 0 && rr<=N && cc>0 && cc<=N){

//                 if(mp[rr][cc] < shark && mp[rr][cc] != 0){
                    
//                     mp[rr][cc] = 0;

//                     res = res + ret.val+1;
//                     sharkCount++;
//                     if(sharkCount == shark){                        
//                         sharkCount = 0; 
//                         shark++;
//                     }
                    
//                     while(!q.empty()) q.pop();

//                     memset(ch, false, sizeof(ch));
//                     q.push(fish(rr, cc, 0));
//                     break;
//                 }
//                 else{
                    
//                     ch[rr][cc] = true;
//                     q.push(fish(rr,cc,ret.val+1));
//                 }
//             }
//         }
//     }
    
//     return res;
// }

소감

이 문제를 해결할때 생각하지 못했던 반례가 있다. 나는 맨 처음에 위, 왼쪽, 오른쪽, 아래쪽 순서로 dy, dx를 구현하였는데 이렇게 순차적으로 구현해서 답이 나오자마자 출력하면 결국 맨위, 맨 왼쪽이라는 조건을 만족할 수 없다.

다음 사진은 백준 사이트에서 찾아온 반례이다. 나는 이런 반례를 생각지 못했기 때문에 많이 헤맸다. 따라서 다음에도 이러한 비슷한 문제를 해결할 경우 반드시 이부분을 기억할 것이다.