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

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

16236번: 아기 상어

문제 풀이
NxN 크기 공간에 물고기 M마리와 아기상어 1마리 존재
최초 아기 상어 크기 2, 아기 상어는 1초에 상하좌우 인접한 한칸씩 이동
아기 상어는 자기보다 큰 물고기가 있는 칸은 지나갈 수 없음.
아기 상어는 자신보다 작은 물고기만 먹을 수 있음.
크기가 같은 물고기는 먹을 수 없지만 지나갈 수는 있음.
물고기 사이즈 1~6
아기 상어 이동 규칙
1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청.
2. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
3. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
+ 거리가 가까운 물고기가 많다면, 상, 좌 순으로 우선순위 부여.
아기 상어가 해당칸의 물고기를 먹는다면 해당 칸은 빈칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1증가
입력
공간의 상태가 주어짐.
출력
엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간 출력
구현해야할 함수(move)
상어와 특정 물고기 위치로 이동하는 최단거리 이동할 수 없다면 0반환

 

최초풀이(시간초과 오류발생)

move함수를 너무 많이 호출한다...

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

using namespace std;

struct Shark
{
    int R;
    int C;
    int Size;
    int Eat;
};

struct Fish
{
    int R;
    int C;
    int Size;
};

struct pos
{
    int R;
    int C;
    int Count;
};


int map[20][20];
bool check[20][20];
int N;
Shark BS;
//이동 : 상, 좌, 하, 우
int idx[4] = {0,-1,0,1};
int idy[4] = {-1,0,1,0};

bool valid(int r, int c){
    return r>=0 && r<N && c>=0 && c<N;
}

int move(int sR, int sC, int eR, int eC){
    queue<pos>q;
    q.push({sR,sC,0});

    for(int r = 0;r<20;r++){
        for(int c = 0;c<20;c++)
            check[r][c] = false;
    } 

    check[sR][sC] = true;

    //BFS
    while(!q.empty()){
        int R = q.front().R;
        int C = q.front().C;
        int cnt = q.front().Count;
        q.pop();

        for(int i = 0; i<4;i++){
            int nR = R + idy[i];
            int nC = C + idx[i];

            if(valid(nR,nC) == false || map[nR][nC] > BS.Size || check[nR][nC] == true) continue;
            else if(nR == eR && nC == eC){
                cnt++;
                return cnt;
            }
            else{
                cnt++;
                q.push({nR,nC,cnt});
                check[nR][nC] = true;
                cnt--;//중요 
            }
        }
    }

    return 0;
}

//우선순위에 따라 정렬
//거리, 상, 좌 순으로 우선순위가 나옴
bool compare(Fish A, Fish B){
    if(A.Size<BS.Size && B.Size<BS.Size){
        int a = move(BS.R,BS.C,A.R,A.C);
        int b = move(BS.R,BS.C,B.R,B.C);
        if(a==b){
            if(A.R == B.R){
                return A.C<B.C;
            }
            else
                return A.R < B.R;
        }    
        else
            return a<b;
    }
    else
        return A.Size<B.Size;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int answer = 0;
    vector<Fish>F;
    BS.Size = 2;
    BS.Eat = 0;
    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){
                map[i][j] = 0;//중요(이것 때문에 많이 걸림...)
                BS.R = i;
                BS.C = j;
            }
            else if(map[i][j]>0)
                F.push_back({i,j,map[i][j]});
        }
    }

    while(true){
        //물고기를 사이즈 순으로 정렬
        sort(F.begin(), F.end(), compare);

        int T = F.size();

        for(int i = 0;i<F.size();i++){
            if(BS.Size<=F[i].Size) break;
            int temp = move(BS.R, BS.C, F[i].R, F[i].C);
            if(temp == 0)continue;
            else{
                answer += temp;
                BS.Eat++;
                if(BS.Size == BS.Eat){
                    BS.Size++;
                    BS.Eat = 0;
                }
                BS.R = F[i].R;
                BS.C = F[i].C;
                map[F[i].R][F[i].C] = 0;
                F[i].Size = 401;
                F.erase(F.begin() + i);
                break;
            }
        }

        if(T == F.size())
            break;
    }

    cout<< answer <<'\n';

return 0;
}

 

 

최종풀이

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

using namespace std;

struct Shark
{
    int R;
    int C;
    int Size;
    int Eat;
};

struct Fish
{
    int R;
    int C;
    int Size;
    int Dist;
};

struct pos
{
    int R;
    int C;
    int Count;
};


int map[20][20];
bool check[20][20];
int N;
Shark BS;
//이동 : 상, 좌, 하, 우
int idx[4] = {0,-1,0,1};
int idy[4] = {-1,0,1,0};

bool valid(int r, int c){
    return r>=0 && r<N && c>=0 && c<N;
}

int move(int eR, int eC){
    queue<pos>q;
    q.push({BS.R, BS.C,0});

    for(int r = 0;r<20;r++){
        for(int c = 0;c<20;c++)
            check[r][c] = false;
    } 

    check[BS.R][BS.C] = true;

    //BFS
    while(!q.empty()){
        int R = q.front().R;
        int C = q.front().C;
        int cnt = q.front().Count;
        q.pop();

        for(int i = 0; i<4;i++){
            int nR = R + idy[i];
            int nC = C + idx[i];

            if(valid(nR,nC) == false || map[nR][nC] > BS.Size || check[nR][nC] == true) continue;
            else if(nR == eR && nC == eC){
                cnt++;
                return cnt;
            }
            else{
                cnt++;
                q.push({nR,nC,cnt});
                check[nR][nC] = true;
                cnt--;//중요 
            }
        }
    }

    return 0;
}

//우선순위에 따라 정렬
//거리, 상, 좌 순으로 우선순위가 나옴
bool compare(Fish A, Fish B){
    if(A.Size<BS.Size && B.Size<BS.Size){
        if(A.Dist==B.Dist){
            if(A.R == B.R){
                return A.C < B.C;
            }
            else
                return A.R < B.R;
        }    
        else
            return A.Dist < B.Dist;
    }
    else
        return A.Size<B.Size;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int answer = 0;
    vector<Fish>F;
    BS.Size = 2;
    BS.Eat = 0;
    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){
                map[i][j] = 0;//중요(이것 때문에 많이 걸림...)
                BS.R = i;
                BS.C = j;
            }
            else if(map[i][j]>0)
                F.push_back({i,j,map[i][j]});
        }
    }

    while(true){
        //물고기를 사이즈 순으로 정렬
        for(int i = 0;i<F.size();i++)
            F[i].Dist = move(F[i].R,F[i].C);

        sort(F.begin(), F.end(), compare);

        int T = F.size();

        for(int i = 0;i<F.size();i++){
            if(BS.Size<=F[i].Size) break;
            int temp = F[i].Dist;
            if(temp == 0)continue;
            else{
                answer += temp;
                BS.Eat++;
                if(BS.Size == BS.Eat){
                    BS.Size++;
                    BS.Eat = 0;
                }
                BS.R = F[i].R;
                BS.C = F[i].C;
                map[F[i].R][F[i].C] = 0;
                F.erase(F.begin() + i);
                break;
            }
        }

        if(T == F.size())
            break;
    }

    cout<< answer <<'\n';

return 0;
}

*문제 풀면서 느낀점

부분적으로 예외처리와 시간절약을 위해 최초 문제상황을 개선하는 시간을 많이 사용했다.

문제를 좀더 분석적으로 접근할 필요가 있을 것같다.