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

• 문제

• 풀이 과정

• 초기 과정

• 최종 코드

• 잡담

백준 16236 : 아기상어
난이도 : 골드 3

시간 : 1시간 30분 소요

 

 

 

문제

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

16236번: 아기 상어

 

풀이 과정

 

문제를 이해하고, 어떻게 풀어야 할 지 생각하는데는 오랜 시간이 걸리지 않았지만 구현 및 디버그하는데 많은 시간을 사용했다.

 

초기 과정

먼저 크게 bfs를 사용해서 구현할 수 있다.

처음에는 next 라는 벡터를 사용하지 않았다.

왜냐하면 위, 왼, 오른, 아래 순서로 탐색순서만 조정한다면 문제가 풀릴 줄 알았다.

 

하지만 생각을 해보니, 현재 위치에서 오른->오른 보다 왼->아래를 먼저 탐색한다는 것을 깨달았다.

그래서 일단 가능한 경우의 수를 next라는 벡터에 다 넣고, bfs가 끝나면 적절한 위치를 찾는 것으로 변경시켰다.

 

int s[MAX][MAX] : 상어 정보 저장하는 2차원 배열

int shark = 2: 상어 크기

int cnt : 현재 크기에서 잡아먹은 양

int sec : 생존 시간

int d[MAX][MAX] = {0, }; : 현재 상어로부터의 거리
    
int mini = INT_MAX : 최소 거리를 저장하는 변수

vector<pair<int, int>> next : 최소 거리가 중복일 때 일단 벡터에 넣기 위한 변수

 

1. 현재 위치에서 잡아 먹을 수 있는 물고기를 bfs로 탐색한다. 잡아먹을 수 있다면 vector<pair<int, int>>에 넣는다.

2. vector에서 거리가 같다면 좌표상 y가 낮은, y가 같다면 x가 낮은 좌표로 이동 및 잡아먹음을 한다.

3. 현재 크기와 잡아먹은 물고기를 비교하여 성장이 필요하면 성장시키고, 다시 1번을 반복한다.

 

4. vector에 들어있는 요소가 없다면, 잡아먹을 수 있는 물고기가 더이상 없다는 의미이므로 종료한다.

4-1. 종료되었다면 여태 저장한 시간을 출력한다.

 

 

최종 코드

#include <iostream>
#include <queue>
#include <climits>
#include <algorithm>

using namespace::std;

#define MAX 21

int s[MAX][MAX];
int N;

pair<int, int> cur;

int shark = 2;  // 초기 상어 사이즈
int cnt = 0;
int sec = 0;

int ud[4] = {-1,0,0,1};
int lr[4] = {0,-1,1,0};


bool bfs(int y, int x){
    queue<pair<int, int>> q;
    q.push({y,x});
    int visited[MAX][MAX] = {0, };
    int d[MAX][MAX] = {0, };
    visited[y][x] = 1;
    s[y][x] = 0;
    int mini = INT_MAX;
    vector<pair<int, int>> next;
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            
            if(ny>=1 && nx>=1 && ny<=N && nx<=N){
                if(s[ny][nx] <= shark && visited[ny][nx] == 0){
                    if(s[ny][nx] != 0 && s[ny][nx] < shark && d[ty][tx]+1 <= mini){
                        next.push_back({ny, nx});
                        q.push({ny, nx});
                        visited[ny][nx] = 1;
                        d[ny][nx] = d[ty][tx] + 1;
                        mini = d[ny][nx];
                    }else{
                        q.push({ny, nx});
                        visited[ny][nx] = 1;
                        d[ny][nx] = d[ty][tx] + 1;
                    }
                }
            }
            
        }
    }
    
    if(!next.empty()){
        cnt++;
        sort(next.begin(), next.end());
        int n1 = next.front().first;
        int n2 = next.front().second;
        cur = {n1,n2};
        sec += d[n1][n2];
        s[n1][n2] = 0;
        return true;
    }else{
        return false;
    }
}

int main(){
    scanf("%d", &N);
    
    for(int i=1; i<=N; i++){
       for(int j=1; j<=N; j++){
           scanf("%d", &s[i][j]);
           if(s[i][j] == 9){
               cur = {i, j};
           }
        }
    }
    
    while(1){
        int t1 = cur.first;
        int t2 = cur.second;
        if(!bfs(t1, t2)){
            printf("%d\n", sec);
            return 0;
        }else{
            if(shark == cnt){
                shark++;
                cnt = 0;
            }
        }
    }
}

 

 

 

잡담

컴파일 에러 : sort() include를 못시킴

 

구현하는데 시간이 꽤 오래걸렸다.