[ BOJ - 16236번 ] 아기 상어 (C++)

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

 

아기 상어는 처음에 크기가 2이고, 같은 크기의 물고기는 지나갈 수 있지만 먹을 수는 없다.

 이동에는 시간이 걸리지만 먹는 데에는 시간이 걸리지 않아서 물고기를 먹는 것은 물고기가 있는 칸으로 이동하면서 칸에 있던 물고기를 없애주는 것과 같다.

 

 처음에 같은 크기의 물고기도 먹을 수 있다고 착각해서 예제 테스트의 결과가 어떻게 나오는 것인지 고민하다 시간을 허비했다. 최근 문제의 조건을 정확히 파악하지 못해 시간을 허비하는 일이 많아졌으니 앞으로 이 점을 유의해서 풀어야 할 것이다.

 

[ 풀이 방법 ]

 

 1. 아기 상어 이동 기능

    - 남은 먹을 수 있는 물고기 수 확인 기능 -> 먹을 수 있는 물고기 수가 0이라면 종료

    - 가장 가까운 물고기 찾는 기능

        - 거리 동일한 물고기 많다면 가장 위 물고기 -> y좌표도 동일하다면 가장 왼쪽 물고기 순서로 탐색

    - 이동에 1초가 걸리고 시간을 세주어야 한다.

      - 예외 상황: 이동이 불가능한 경우? ex) 남은 물고기가 있지만 크기가 더 큰 물고기에 둘러쌓인 경우

2. 물고기 먹는 기능

    - 물고기 먹으면 그 칸은 빈칸이 되고, 따로 시간을 추가로 세지 않는다.

    - 물고기 먹은 개수를 세고, 자기 크기와 동일한 개수를 먹으면 아기 상어의 크기를 1 키운다.

 

 위의 예외 상황을 처리하면서 기능을 구현할 수 있도록 BFS를 사용해 구현했다.

 현재 위치를 기준으로 위쪽 -> 왼쪽 -> 아래쪽 -> 오른쪽 순서로 BFS를 실행하도록 구현했고, 물고기를 먹을 때마다 BFS를 종료하고 현재 위치를 갱신한 뒤 다시 BFS를 반복하도록 구현하였다.

 큐에 원소를 삽입하는 조건을 이용해 예외 상황을 처리하면서도 가장 위쪽 -> 왼쪽 순서로 물고기를 탐색할 수 있었다.

 

 그러나 변수가 두 가지 발생했는데,

 첫 번째는 위 순서대로 실행하면 오른쪽보다 아래쪽을 먼저 탐색하기 때문에 가장 위쪽을 먼저 탐색한다는 조건에 위배되게 된다.

따라서 위쪽 -> 왼쪽 -> 오른쪽 -> 아래쪽 순서대로 탐색하도록 수정했다.

 

 두 번째는 위의 방법으로 수정해도 거리가 1보다 클 경우, 순서가 맞지 않는 경우가 생겼다.

예를 들어, 

9는 상어, 1은 물고기일 때:
0 0 9 0 1
0 1 0 0 0

 

 위의 경우에 첫 반복에서 왼쪽 -> 오른쪽 -> 아래쪽 순서로 큐에 들어가게 되고, 그 순서대로 다음 반복이 실행되기 때문에 문제의 조건을 만족하기 위해서는 오른쪽에 있는 1을 먼저 먹어야 하지만 왼쪽 아래에 있는 1을 먹게 된다.

위쪽: 이동 불가능
왼쪽: 이동 가능하므로 큐에 먼저 들어가게 됨
오른쪽: 이동 가능하므로 큐에 들어가게 되지만 왼쪽보다 늦게 큐에서 꺼내지게 됨
따라서 왼쪽 아래로 이동하는 코드가 오른쪽의 오른쪽으로 이동하는 코드보다 먼저 실행되게 되므로 왼쪽 아래로 이동해 물고기를 먹은 뒤 현재 위치가 갱신 된 후 BFS가 종료된다. -> 오류

 

 

 이 문제를 해결하기 위해 priority queue를 사용해 큐에 들어있는 원소가조건에 맞게 정렬되도록 구현했다.

struct Shark {
    int x; int y; // 행과 열
    int size;
    int time; // 이동 시간
};

struct cmp {
    bool operator()(Shark& s1, Shark& s2) {
    	// 거리가 같고 위쪽으로의 거리가 같다면, 왼쪽에 있는 것이 먼저 오도록 정렬 
        if(s1.time == s2.time && s1.x == s2.x) return s1.y > s2.y;
	// 거리가 같다면, 위쪽에 있는 것이 먼저 오도록 정렬
        if(s1.time == s2.time) return s1.x > s2.x;
	// 거리가 짧은 것이 먼저 오도록 정렬
        return s1.time > s2.time;
    }
};

priority_queue<Shark, vector<Shark>, cmp> pq;

 

 또한 큐에 원소가 들어있는 순서를 활용하기 위해서,

 원소를 큐에 넣기 전에 물고기의 크기와 상어의 크기를 비교하여 먹을 수 있다면 현재 좌표를 갱신하고 BFS를 종료하던 기존의 코드를 수정하여 큐에서 원소를 꺼낸 직후 위 로직을 수행하도록 수정했다.

 

 

[ 정답 코드 ]

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

using namespace std;

struct Shark {
    int x; int y;
    int size;
    int time;
};

struct cmp {
    bool operator()(Shark& s1, Shark& s2) {
        if(s1.time == s2.time && s1.x == s2.x) return s1.y > s2.y;
        if(s1.time == s2.time) return s1.x > s2.x;
        return s1.time > s2.time;
    }
};

int N;
vector<vector<int>> map;

int curX;
int curY;
int curSize = 2;
bool fish = true;

int dirX[4] = {-1, 0, 0, 1};
int dirY[4] = {0, -1, 1, 0};

int res = 0;
int cnt = 0;

void bfs(vector<vector<bool>>& visited) {
    priority_queue<Shark, vector<Shark>, cmp> pq;
    pq.push({curX, curY, curSize, 0});
    visited[curX][curY] = true;
    
    while (!pq.empty()) {
        int x = pq.top().x;
        int y = pq.top().y;
        int size = pq.top().size;
        int time = pq.top().time;
        
        pq.pop();
        
        if(map[x][y] != 0 && map[x][y] < size) {
            map[x][y] = 0;
            curX = x;
            curY = y;
            res += time;
            cnt++;
            if(cnt >= size) {
                size++;
                cnt = 0;
            }
            curSize = size;
            
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dirX[i];
            int ny = y + dirY[i];
            
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) continue;
            
            visited[nx][ny] = true;
            
            if(map[nx][ny] > size) {
                continue;
            } else {
                pq.push({nx, ny, size, time+1});
            }
        }
    }
    
    fish = false;
    return;
}

void solve() {
    
    while(fish) {
        vector<vector<bool>> visited(N, vector<bool>(N));
        bfs(visited);
        vector<vector<bool>>().swap(visited);
    }
}

int main() {
    
    iostream::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    
    map.resize(N, vector<int>(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;
                curX = i;
                curY = j;
            }
        }
    }
    
    solve();
    
    cout << res << '\n';
    
    return 0;
}