16236 아기상어

 

시뮬레이션 문제를 해결해보자.

맵이 주어지고, 탐색을 할 경우에 dfs를 쓸 것인지, bfs를 쓸 것인지 고민이 된다.

bfs가 dfs를 아우르는 개념이라서 보통 bfs를 쓰면 되는데,

특히 최단경로 문제(가중치가 없을 때)일 때는 bfs를 써야한다.

이 때, visited[][] 대신, dist[][]를 이용하면서 최단경로도 저장하고, 방문했는지도 체크할 수 있다.

 

처음에 문제를 이해하느라, 시간을 많이 썼지만

차근차근 이해하고, 배운 개념을 써먹으면 문제가 풀린다.

 

시간복잡도는 

모든 물고기 O(V)에 대해

한번 잡아먹을 때마다 다음 잡아먹을 물고기 모두를 탐색해야 하므로 O(|V| + |E|)가 걸린다.

O((20 x 20) x (20 x 20 + 19 x 20 x 2) ) = 464,000이 걸린다.

#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

int N;
int a[20][20];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int cursize = 2;
int dist[20][20];
bool eatable;
const int INF = 0x7fffffff;
int ans;

struct Shortest{
    int x, y;
    int dif;
};
Shortest shortest;

void initDist(){
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            dist[i][j] = -1;
        }
    }
}

void bfs(int start_x, int start_y){
    eatable = false;
    initDist();
    dist[start_x][start_y] = 0;
    shortest = {INF, INF, INF};

    queue<pair<int, int> > q;
    q.push({start_x, start_y});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i=0; i<4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < N && 0 <= ny && ny < N
                && (dist[nx][ny] == -1) && a[nx][ny] <= cursize){
                dist[nx][ny] = dist[x][y] + 1;
                if (0 < a[nx][ny] && a[nx][ny] < cursize){
                    eatable = true;
                    int dif = dist[nx][ny];
                    if (shortest.dif > dif) shortest = {nx, ny, dif};
                    else if (shortest.dif == dif) {
                        if (shortest.x > nx) shortest = {nx, ny, dif};
                        else if (shortest.x == nx){
                            if (shortest.y > ny) shortest = {nx, ny, dif};
                        }
                    }
                }
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    scanf("%d", &N);
    int x, y;
    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            scanf("%d", &a[i][j]);
            if (a[i][j] == 9) { x = i; y = j; }
        }
    }
    int cnt = 0;
    while(true){
        // Find the fish that has the shortest distance.
        bfs(x, y);
        if (!eatable) break;

        // Go and eat
        a[x][y] = 0;
        x = shortest.x;
        y = shortest.y;
        a[x][y] = 9;
        ans += shortest.dif;
        ++cnt;
        if (cnt == cursize){
            ++cursize;
            cnt = 0;
        }
    }
    printf("%d\n", ans);
    return 0;
}