[백준/c++] 16236번 아기상어

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

16236번: 아기 상어

0. 잡설

시뮬레이션 문제에 자신이 없어서 헤매다가, 좀 풀어보니 감이 좀 잡혔습니다.
시뮬레이션에서는 문제의 모듈화가 중요한 것 같습니다.
디버깅도 쉬워지고, 요새 코테에서 많이 사용하는 프로그래머스에서도 solve()모듈을 주니까 모듈화에 이점이 많은 것 같습니다.

또, 모듈화를 하면 중간중간 프린트를 찍어볼 때 어떤 모듈에서 생각대로 움직여주지 않는지 확인할수도 있겠죠!!

 

1. 접근 방식

크게, 현재 상어가 있는 곳에서 BFS -> 물고기 먹기 -> 먹을 수 있는 물고기가 없으면 현재 흐른 시간을 프린트하고 종료
의 순서를 반복했습니다.

다만, 처음 상어의 크기가 2이고, 상어의 크기와 같은 수의 물고기들을 먹어 치워야 상어의 크기가 1이 커진다는 조건을 처음에 놓쳐서 '틀렸습니다'를 조금 받았습니다. 예를 들어, 상어의 크기는 처음에 2이므로 두마리의 물고기를 먹어야 크기가 3이 되고, 크기가 3이 된 상어는 물고기를 3마리 먹어야 크기가 4가 됩니다.

 

2. 모듈 코드 설명

가) 입력

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

int field[25][25];
int visited[25][25];

int n;
int up_time=0;

int nx[] = {0, 1, 0, -1};
int ny[] = {1, 0, -1, 0};

pair<int, int> now_shark;
int shark_size = 2;
int eat_cnt = 0;

void input(){
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>field[i][j];
            if(field[i][j] == 9) {
                field[i][j] = 0;
                now_shark = {i, j};
            }
        }
    }
}

전역 변수로 설정된 2차원 int 배열 field에 현재 어장의 상태를 입력받습니다.

주의 하실 점은, 현재 상어의 위치인 9가 입력될 때 now_shark에 상어의 현재 위치를 업데이트 합니다.

field에 9를 그대로 입력하면, 상어의 크기가 9 이상으로 커졌을 때 본인을 먹는 무한루프의 우려가 있습니다.

 

나) 먹이 탐색하기 (BFS)

vector<pair<int, pair<int, int> > > find_food(){
    //시간, x좌표, y좌표
    vector<pair<int, pair<int, int> > >food_dir;
    
    queue<pair<int, int> > q;
    q.push({now_shark.first, now_shark.second});
    visited[now_shark.first][now_shark.second] = 1;
    
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        
        q.pop();
        for(int i=0; i<4; i++){
            int dx = now_x + nx[i];
            int dy = now_y + ny[i];
            
            if(0<=dx && dx < n && 0<=dy && dy < n){
                if(visited[dx][dy] != 0) continue;
                if(field[dx][dy] > shark_size) continue;
                else if(field[dx][dy] == shark_size || field[dx][dy] == 0){
                    q.push({dx, dy});
                    visited[dx][dy] = visited[now_x][now_y]+1;
                    continue;
                }
                else if(field[dx][dy] < shark_size){
                    food_dir.push_back({visited[now_x][now_y], {dx, dy}});
                }
            }
        }
    }
    
    return food_dir;
}

3차원 벡터를 반환하는 BFS입니다. 3차원 벡터의 순서는 <먹이와의 거리, {먹이의 X좌표, 먹이의 Y좌표}>입니다.

상어의 최초 위치를 visited[상어 X][상어 Y] = 1로 하는 BFS를 수행했습니다. 질문 게시판을 보니 DFS는 시간초과가 나는 것 같습니다.

저는 BFS과정 중에서 먹이의 가능성이 있는 좌표만 벡터에 추가하여 반환하도록 하였습니다. 이렇게 하면 먹이의 갯수(벡터의 사이즈)로 종료 조건을 확인할 수 있으니까요!

 

큐에 좌표가 들어가는 코드를 자세히 보겠습니다. 해당 위치에서 먹이를 먹을 수 있는지, 없는지 판단합니다. 먹을 수 있다면, 좌표에 추가합니다.

if(0<=dx && dx < n && 0<=dy && dy < n){
                if(visited[dx][dy] != 0) continue; // 1번
                if(field[dx][dy] > shark_size) continue; // 2번
                else if(field[dx][dy] == shark_size || field[dx][dy] == 0){
                //3번
                    q.push({dx, dy});
                    visited[dx][dy] = visited[now_x][now_y]+1;
                    continue;
                }
                else if(field[dx][dy] < shark_size){
                //4번
                    food_dir.push_back({visited[now_x][now_y], {dx, dy}});
                }
            }

1번 if문 : visited면 continue합니다.

2번 if문: 먹이의 크기가 현재 상어의 크기보다 크면 continue합니다.

3번 else if문: 먹이의 크기가 상어의 크기와 같거나 0이면 통과할 수 있으므로 q에 push합니다.

4번 else if문: 먹이의 크기가 상어보다 작아서 먹을 수 있다면 3차원 벡터에 현재 먹이의 거리와 위치를 추가합니다.

* 먹이를 먹을 수 있다고 하여 bfs를 종료하면 여러 먹이가 있는 경우의 처리를 할 수 없습니다!!

 

다) 먹을 수 있는 먹이 파악하기

int eat_food(vector<pair<int, pair<int, int> > > food_dir){
    if(food_dir.size() == 0){
        cout<<up_time;
        return 0;
    }
    else if(food_dir.size() == 1){
        up_time += food_dir[0].first;
        eat_cnt++;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        
        field[now_shark.first][now_shark.second] = 0;
        now_shark.first = food_dir[0].second.first;
        now_shark.second = food_dir[0].second.second;
        field[now_shark.first][now_shark.second] = 0;
        return 1;
    }
    else{
        sort(food_dir.begin(), food_dir.end());
        
        int min_dir_target = food_dir[0].first;
        int most_top = 100000, most_left = 1000000;
        int idx = 0;
        
        for(int i=0; i<food_dir.size(); i++){
            if(food_dir[i].first == min_dir_target){
                if(food_dir[i].second.first < most_top){
                    most_top = food_dir[i].second.first;
                    most_left = food_dir[i].second.second;
                    idx = i;
                }
                if(food_dir[i].second.first == most_top){
                    if(food_dir[i].second.second < most_left){
                        most_left = food_dir[i].second.second;
                        idx = i;
                    }
                }
            }
            
        }
        
        up_time += food_dir[idx].first;
        eat_cnt++;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        field[now_shark.first][now_shark.second] = 0;
        now_shark.first = food_dir[idx].second.first;
        now_shark.second = food_dir[idx].second.second;
        field[now_shark.first][now_shark.second] = 0;
        
        return 1;
    }
}

핵심 부분입니다. 먹을 수 있는 먹이를 파악합니다.

나) 먹이 탐색하기의 결과 3차원 벡터를 파라미터로 받습니다.

 

i) 입력받은 먹이의 벡터의 길이가 0이면, 먹을 물고기가 없는 상태이므로 현재까지 흐른 시간을 출력하고 종료합니다.
0을 반환하여 프로그램이 종료되어야 함을 알립니다.

 

ii) 입력받은 먹이의 벡터의 길이가 1이면, 먹을 수 있는 물고기는 1마리입니다.
따라서 먹이를 먹어 치워서 해당 부분의 field를 0으로 바꾸고, 상어의 위치를 업데이트 합니다. 

먹이까지의 거리를 up_time에 추가합니다.

 

iii) 입력받은 먹이의 벡터의 길이가 2이상이면, 먹을 수 있는 물고기의 후보는 여러마리입니다.

먹이의 길이가 가까운 것 -> 가장 위쪽에 있는 것 -> 가장 왼쪽에 있는 것이 이 경우 먹어치울 물고기이므로,

먹이 벡터를 오름차순 정렬하여 Brute force를 진행합니다.

가장 가까운 거리인 0번째 위치의 거리 기준이 같으면서, 가장 위쪽, 가장 왼쪽에 있는 먹이를 먹어치웁니다.

 

3. 정답 코드

//
//  아기 상어.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/01/19.
//

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

int field[25][25];
int visited[25][25];

int n;
int up_time=0;

int nx[] = {0, 1, 0, -1};
int ny[] = {1, 0, -1, 0};

pair<int, int> now_shark;
int shark_size = 2;
int eat_cnt = 0;

void print_field(int stage, int time){
    cout<<stage<<"번째 상황 -> 현재 시간 : "<<up_time <<"\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) cout<<field[i][j]<<" ";
        cout<<"\n";
    }
}
void print_visited(int stage){
    cout<<stage<<"번째 VISITED : \n";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) cout<<visited[i][j]<<" ";
        cout<<"\n";
    }
}

void input(){
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>field[i][j];
            if(field[i][j] == 9) {
                field[i][j] = 0;
                now_shark = {i, j};
            }
        }
    }
}

void clear_visited(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) visited[i][j] = 0;
    }
}

vector<pair<int, pair<int, int> > > find_food(){
    //시간, x좌표, y좌표
    vector<pair<int, pair<int, int> > >food_dir;
    
    queue<pair<int, int> > q;
    q.push({now_shark.first, now_shark.second});
    visited[now_shark.first][now_shark.second] = 1;
    
    while(!q.empty()){
        int now_x = q.front().first;
        int now_y = q.front().second;
        
        q.pop();
        for(int i=0; i<4; i++){
            int dx = now_x + nx[i];
            int dy = now_y + ny[i];
            
            if(0<=dx && dx < n && 0<=dy && dy < n){
                if(visited[dx][dy] != 0) continue;
                if(field[dx][dy] > shark_size) continue;
                else if(field[dx][dy] == shark_size || field[dx][dy] == 0){
                    q.push({dx, dy});
                    visited[dx][dy] = visited[now_x][now_y]+1;
                    continue;
                }
                else if(field[dx][dy] < shark_size){
                    food_dir.push_back({visited[now_x][now_y], {dx, dy}});
                }
            }
        }
    }
    
    return food_dir;
}

int eat_food(vector<pair<int, pair<int, int> > > food_dir){
    if(food_dir.size() == 0){
        cout<<up_time;
        return 0;
    }
    else if(food_dir.size() == 1){
        up_time += food_dir[0].first;
        eat_cnt++;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        
        field[now_shark.first][now_shark.second] = 0;
        now_shark.first = food_dir[0].second.first;
        now_shark.second = food_dir[0].second.second;
        field[now_shark.first][now_shark.second] = 0;
        return 1;
    }
    else{
        sort(food_dir.begin(), food_dir.end());
        
        int min_dir_target = food_dir[0].first;
        int most_top = 100000, most_left = 1000000;
        int idx = 0;
        
        for(int i=0; i<food_dir.size(); i++){
            if(food_dir[i].first == min_dir_target){
                if(food_dir[i].second.first < most_top){
                    most_top = food_dir[i].second.first;
                    most_left = food_dir[i].second.second;
                    idx = i;
                }
                if(food_dir[i].second.first == most_top){
                    if(food_dir[i].second.second < most_left){
                        most_left = food_dir[i].second.second;
                        idx = i;
                    }
                }
            }
            
        }
        
        up_time += food_dir[idx].first;
        eat_cnt++;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        field[now_shark.first][now_shark.second] = 0;
        now_shark.first = food_dir[idx].second.first;
        now_shark.second = food_dir[idx].second.second;
        field[now_shark.first][now_shark.second] = 0;
        
        return 1;
    }
}
void solve(){
    input();
    int stage = 1;
    while(1){
        clear_visited();
        vector<pair<int, pair<int, int> > > food_dir = find_food();
//        print_visited(stage);
        int check = eat_food(food_dir);
        if(check == 0) break;
//        print_field(stage++, up_time);
        food_dir.clear();
    }
    
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    solve();
    return 0;
}

solve의 print_visited와 print_field를 주석 해제하여 현재 상황을 확인하실 수 있습니다.