백준 16236

이 문제는 꽤나 고전을 했던 것 같다.

이번에도 bfs 문제인데

문제도 꽤나 길고 조건도 많아서 차근히 정리하고 푸는 것을 추천한다.

먼저 조건부터 정리하자면

- 상어는 상하좌우 4방향으로 움직인다.

- 상어는 자기보다 크기가 작은 물고기만 먹을 수 있으며, 같다면 지나갈 수 있고, 물고기가 더 크다면 지나갈 수 없다.

- 상어가 더 이상 먹을 수 있는 물고기가 없다면 엄마 상어에게 도움을 요청한다 = 알고리즘이 종료한다.

- 먹을 수 있는 물고기가 다수라면 가장 가까운 물고기를 향해 가며, 거리가 가깝다면 가장 위쪽, 그마저 윗방향으로 같은 값이라면 가장 왼쪽에 있는 물고기를 먹으러 간다.

 

그럼 이쯤에서 코드를 봐보자.

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

struct shark{
    int x, y;
} typedef shark;

int n;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int a[20][20];
int dist[20][20] = {0, };
int minVal;
shark dest;

bool isIn(shark s){
    if(s.x < 0 || s.y < 0 || s.x >= n || s.y >= n) return false;
    return true;
}

void bfs(int size){
    queue<shark> q;
    q.push(dest);
    dist[dest.x][dest.y] = 0;
    while(!q.empty()){
        shark node = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            shark next = {node.x+dx[i], node.y+dy[i]};
            if(isIn(next) && dist[next.x][next.y] == -1){
                if(a[next.x][next.y] > size) continue;
                dist[next.x][next.y] = dist[node.x][node.y] + 1;
                if(a[next.x][next.y] != 0 && a[next.x][next.y] < size){
                    if(minVal > dist[next.x][next.y]) {
                        minVal = dist[next.x][next.y];
                        dest = {next.x, next.y};
                    }
                    else if(minVal == dist[next.x][next.y]){
                        if(dest.x == next.x){
                            if(dest.y > next.y){
                                dest = {next.x, next.y}; 
                            }
                        }else if(dest.x > next.x){
                            dest = {next.x, next.y};
                        }
                    }
                }
                q.push(next);
            }
        }
    }
}

void init(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            dist[i][j] = -1;
        }
    }
    minVal = 500;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
            if(a[i][j] == 9) {
                dest = {i, j};
                a[i][j] = 0;
            }
        }
    }

    int size = 2;
    int eat = 0;
    int ans = 0;
    while(true){
        shark prev = dest;
        init();
        bfs(size);
        if(!(prev.x == dest.x && prev.y == dest.y)){
            eat++;
            a[dest.x][dest.y] = 0;
            if(eat == size) {
                size++;
                eat = 0;
            }
            ans += dist[dest.x][dest.y];
        }
        else break;
    }

    cout << ans;
}

이번엔 코드가 좀 길지만 크게 전역변수와 init, bfs, while loop(in main) 네가지로 나누어 보겠다.

변수부터 보자면

dist 배열은 해당 좌표로 가는데 최단거리,

minVal은 해당 루틴 bfs에서 최단거리값이며 dest는 minVal만큼 걸린 좌표값이다.

 

init 함수는 dist 배열과 minVal 값을 초기화하기 위함이다.

 

bfs 함수는 상어의 현 위치에서 가장 가까운 먹을 수 있는 물고기가 위치한 곳까지의 좌표와 거리를 구하기 위한 함수이다.

 

while loop(in main)은 bfs를 통해 얻은 dist 값을 ans 값에 더하여 나가며, 더 이상 먹을 수 있는 물고기가 없을 때까지 bfs를 진행하여 가능한 목적지 값과 그 값까지의 거리를 계산한다.

 

간단하게 보면 이렇게인데 달리 설명이 필요할만한 부분은 더 없을 거라 본다.

 

사실 처음에 이 풀이를 생각지 못 했던 것은 아니나, 선뜻 실행하지 못했던 것은 "시간 안에 풀 수 있을까?"였다.

막연하게 bfs를 이렇게 많이 수행하면 못 풀 것 같은데...라고 생각했던 것이 컸다.

 

그리고 시간복잡도를 계산한 결과 bfs를 한번 시행하는 데 O(n + e), 해당 bfs를 n번(모든 좌표에 대해 bfs 시행) 시행하여 O(n * n) = O(n^2), 그리고 위 로직을 모든 먹을 수 있는 물고기에 대하여 행함으로 O(n^2 * n^2) = O(n^4)이다.

20 ^ 4 = 160,000으로 1초에 1억번의 연산을 한다고 하였을 때 충분히 연산이 시행될 수 있다.

(나는 막연히 될까..라고 생각했는데 말이다...)

나에게 쉽지는 않았지만, 이번 기회로 더욱 시간 복잡도 계산이 중요하다는 것을 깨달았고, 앞으로는 문제에 단순히 매달리기 보다는 내가 생각한 로직의 시간복잡도도 계산하여 풀 수 있는 문제를 풀지 못 하는 경우와 잘못된 풀이에 대하여 매달리는 경우를 줄일 수 있도록 노력해가야 하겠다.