[BaekJoon/백준] 16236번 아기 상어

 

동요를 떠올리게 해주는 문제

 

 

문제의 키포인트는 아래와 같다.

 

1. BFS를 통해, 다음으로 먹을 물고기 위치 탐색

2. 이동 후 먹은 뒤 반복

 

 

처음에는, 그냥 BFS 없이 2중 포문으로 연산하고, 거리를 맨헤튼 거리로 계산했었는데 이는 잘못된 방법이었다.

왜냐하면, 아기상어는 자신보다 큰 물고기가 위치한 곳으로는 갈 수 없기 때문이다.

 

 

주석을 아주 세세하게 달아놨는데, 흐름은 이렇다

 

a. 아기상어 시작 위치 저장

b. 아기상어 시작 위치에서 bfs를 돌면서, 먹을 수 있는 물고기들을 찾을 때 마다 {그곳까지의 거리, 맵에서의 절대적인 위치} 를 저장한다.

그곳까지의 거리는 초수계산을 위해 사용되고, 맵에서의 절대적인 위치는 우선순위를 따지기 위해 사용된다.

c. 이를 토대로 cmp 비교함수로 정렬을 해준다

d. 정렬 후 맨 앞에 있는 것이 아기상어가 먹을 물고기이다. 이 값을 토대로 값을 업데이트해준다.

e. 아기상어는 자신의 몸집 크기의 물고기 갯수만큼 먹으면 몸집이 성장한다. 이를 적용해준다.

d. 반복

/*
 distance를 맨헤튼거리로 표현하지 못하는 이유는, 아기상어는 자기보다 큰 물고기를 지나갈 수 없다.
 bfs로 지정해줘야한다.
 */

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

using namespace std;


int N;
int MAP[20][20];
int VISIT[20][20]; // VISIT과 depth 동시에 처리할 예정


int SX, SY, SS; //  아기상어 위치(SX, SY), 아기상어 크기(SS)

int TOTAL_TIME; // == TOTAL_DISTANCE와 같은 의미

int EAT_COUNT; // 먹은 물고기 수 체킹

int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, 1, -1};


vector<pair<int, int>> small_fishes; // {아기상어와의 거리 차이, 배열을 숫자로}


void bfs(int x, int y) {
    
    queue<pair<int ,int>> que;
    
    que.push({x, y});
    VISIT[x][y] = 1; // 방문처리하기위해 1로. 문제에서는 시작지점까지 거리로 포함하지 않으니 맨 마지막에 -1해주면 거리계산됨.
    
    
    while(!que.empty()) {
        
        int xx = que.front().first;
        int yy = que.front().second;
        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = xx + mx[i];
            int ty = yy + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= N)
                continue;
            
            
            if(VISIT[tx][ty] == 0 && MAP[tx][ty] <= SS) { // 지나갈 수 있다면
                
                VISIT[tx][ty] = VISIT[xx][yy] + 1;
                que.push({tx, ty});
                
                if(MAP[tx][ty] > 0 && MAP[tx][ty] < SS) { // 먹을 수 있는 물고기라면
                    
                    int distance = VISIT[tx][ty] - 1; // 맨 첫 지점을 방문처리하기위해 1로 시작했기에 -1해줌.
                    int location = tx * N + ty;
                    
                    small_fishes.push_back({distance, location});
                    
                }
            }
            
        }
        
    }
    
    
}

int cmp(pair<int, int> a, pair<int, int> b) {
    
    if(a.first == b.first)
        return a.second < b.second;
    else
        return a.first < b.first;
    
}


int main() {
    
    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) {
                // 아기상어 위치와 크기 초기화
                SX = i; SY = j; SS = 2;
                
                MAP[i][j] = 0; // 9를 계속 남겨놓으면 이후 작업때 고려사항이 늘어날 수 있으니, 아기상어 위치저장 했으면 0으로 초기화
            }
        }
    }
    
    
    
    while(1) {
        
        small_fishes.clear();
        
        memset(VISIT, 0, sizeof(VISIT));
        bfs(SX, SY);
        
        sort(small_fishes.begin(), small_fishes.end(), cmp);
        
        // 먹을 물고기 없으면 종료
        if(small_fishes.size() == 0)
            break;
        
        
        // 물고기까지 닿는데의 시간 = 거리 더해줌
        TOTAL_TIME += small_fishes.front().first;
        
        // 아기상어 위치를 해당 위치로 재조정
        int xx = small_fishes.front().second / N;
        int yy = small_fishes.front().second % N;

        SX = xx;
        SY = yy;
        
        // 먹은 물고기 자리는 0처리
        MAP[xx][yy] = 0;
        
        // 물고기 하나 먹음 처리
        EAT_COUNT++;
        
        // 먹은 물고기 수가 자신의 크기와 같아야 증가..
        if(SS == EAT_COUNT) {
            SS++;
            EAT_COUNT = 0;
        }
        
    }
    
    cout << TOTAL_TIME << "\n";

}

 

 

소요 시간 : 1시간