[BOJ] #16236 아기 상어

시간 제한	메모리 제한	정답 비율
2 초	512 MB	36.088%

 

16236번: 아기 상어

 

문제

아기 상어가 먹을 수 있는 먹이 중 최단 거리에 있는 먹이를 차례대로 먹어야 한다. 이 때 최단 거리의 먹이가 여러개라면 가장 위쪽에 있는 먹이를 먹고, 최단 거리이면서 위쪽에 있는 먹이가 여러개라면 가장 왼쪽에 있는 먹이를 택한다.

 

해결 방안

'가장 위쪽, 가장 왼쪽' 이라는 말이 사실 이해하기 어려웠는데 이해하고 나면 허무한 얘기였다. 말 그대로 위쪽과 왼쪽을 뜻한 단어로, 최단 거리가 여러개일 때 x좌표가 작은 순서를 우선으로, x좌표가 같고 최단거리인 먹이가 여러개라면 y좌표가 작은 먹이를 우선으로 먹는다는 뜻이다.

상어의 위치를 pair 쌍으로 저장해 두어 매 번 가장 짧은 거리에 있는 먹이를 찾으러 bfs를 돌리게 된다. bfs 를 돌리면서 chk라는 배열을 사용하게 되는데, 이 배열은 방문했는지 체크함과 동시에 방문했을 당시의 시간을 저장한다. 따라서 먹이들을 탐색하면서 먹을수 있고, 최단거리라면 Min(아기 상어와 아기 상어가 먹을 수 있는 먹이의 최단거리)과 Min_p(아기 상어가 먹을 수 있는 먹이 좌표)를 갱신한다. 상어의 크기보다 크거나 이미 탐색한 위치라면 넘어가고, 상어와 크기가 같은 먹이는 지나갈 수만 있으므로 갱신할 필요 없이 다음번 탐색을 위해 큐에 넣는다.

bfs를 끝내고 나면 아기 상어가 먹을 수 있는 최단거리의 먹이를 찾아낸 것이므로 상어의 위치와 초를 갱신한다. 만약 bfs가 끝날 때 까지 찾아낸 최단거리가 없다면 엄마 상어에게 도움을 청해야하므로 프로그램을 종료한다.

메모리	시간
1992 KB	4 ms

#include<iostream>
#include<string.h>
#include<queue>
#define inf 1e9
#define F(x, y, u, p) for(int x = 0; x<u; x++)for(int y = 0; y<p; y++)
using namespace std;
typedef pair<int, int> p;
int n, arr[25][25], chk[25][25], shark_size = 2, Min, cnt, ans;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
p shark, Min_p;
void bfs(int x, int y) {
    queue<p> q;
    q.push({ x, y });
    chk[x][y] = 0;
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i], nc = c + dy[i];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (arr[nr][nc] > shark_size || chk[nr][nc] >= 0) continue;
            
            chk[nr][nc] = chk[r][c] + 1;
            if (arr[nr][nc] && arr[nr][nc] < shark_size) {
                if (Min > chk[nr][nc]) {
                    Min = chk[nr][nc];
                    Min_p.first = nr; Min_p.second = nc;
                }
                else if (Min == chk[nr][nc]) {
                    if (Min_p.first > nr || (Min_p.first == nr && Min_p.second > nc)) {
                        Min_p.first = nr; Min_p.second = nc;
                    }
                }                
            }
            q.push({ nr, nc });
        }
    }
}
int main() {
    scanf("%d", &n);
    F(i, j, n, n) {
        scanf("%d", &arr[i][j]);
        if (arr[i][j] == 9) {
            shark = { i,j }; arr[i][j] = 0;
        }
    }
    while (1) {
        Min = Min_p.first = Min_p.second = inf;
        memset(chk, -1, sizeof(chk));
 
        bfs(shark.first, shark.second);
 
        if (Min == inf) break;
        ans += Min;
        shark = { Min_p.first, Min_p.second };
        arr[Min_p.first][Min_p.second] = 0;
 
        cnt++;
        if (cnt == shark_size) {
            shark_size++;
            cnt = 0;
        }
    }
    printf("%d", ans);
 
    return 0;
}