[백준] 16236번: 아기상어

문제 주소 : www.acmicpc.net/problem/16236

16236번: 아기 상어

문제 확인

 

bfs와 시뮬레이션 문제입니다.

배열 크기가 20x20으로 작기 때문에 가지치기 등을 이용하지 않고 문제를 풀 수 있습니다.

주의할 점은 먹이를 선정하는 기준이 아기 상어로부터의 거리, 거리가 같다면 위, 왼쪽 순으로 우선순위가 높습니다.

먹이를 먹으며 이동한 거리가 최종 결과가 됩니다.

 

풀이

 

큐를 통해서 bfs를 구현하고 visited 배열을 통해 여러 번 탐색하는 것을 방지합니다.

depth에 따라 우선순위, 답을 결정해야 하므로 같은 depth는 한 번에 처리합니다.

같은 depth에서 먹을 수 있는 물고기가 여러마리 나오게 되면 위, 왼쪽 순서로 우선순위를 처리해 결정하게 됩니다.

먹을 물고기가 결정 되면 큐의 모든 내용을 지우고, visited 배열을 초기화하여 새로운 먹이를 탐색하게 됩니다.

이 과정을 반복하여 먹을 수 있는 물고기가 없으며 visited 배열이 모두 1이 되면 큐가 비게 되어 종료하게 됩니다.

 

코드

#include <stdio.h>
#include <string.h>
 
typedef struct node {
    char x, y;
}node;
int main() {
    node que[400];
    short ary[20][20];
    char visited[20][20] = { 0 };
    char dx[] = { -1, 0, 0, 1 },
        dy[] = { 0, -1, 1, 0 },//상왼오하
        n, level = 2, count = 0;
    scanf("%hd\n", &n);
    for (short i = 0; i < n; i++) {
        for (short j = 0; j < n; j++) {
            scanf("%hd", &ary[i][j]);
            if (ary[i][j] == 9) {
                ary[i][j] = 0;
                que[0] = { i, j };
                visited[i][j] = 1;//초기 위치 설정
            }
        }
    }
    short left = 0, right = 1;//큐 인덱스
    short depth = 0, total = 0;//움직인 거리 depth
    while (left < right) {
        short cur_size = right - left;
        char tx = 21, ty = 21;
        while (cur_size--) {//같은 depth의 좌표들을 한번에 처리함
            auto &t = que[left++];
            char cx = t.x, cy = t.y;
            for (short d = 0; d < 4; d++) {
                char nx = cx + dx[d], ny = cy + dy[d];
                if (nx < 0 || n <= nx || ny < 0 || n <= ny) continue;//배열 밖
                if (visited[nx][ny] || ary[nx][ny] > level) continue;//탐색 하였거나 먹을 수 없는 물고기
                else if (!ary[nx][ny] || ary[nx][ny] == level) {//먹지 못하지만 지나갈 수 있는 물고기, 빈칸
                    que[right++] = { nx, ny };
                    visited[nx][ny] = 1;
                }
                else if (ary[nx][ny] < level) {//먹을 수 있는 물고기
                    if (tx > nx || (tx == nx && ty > ny)) {//상, 왼 순서로 좌표 우선순위 결정 
                        tx = nx;
                        ty = ny;
                    }
                }
            }
        }
        depth++;//이동횟수
        if (tx != 21 && ty != 21) {//먹을 물고기가 결정됨
            ary[tx][ty] = 0;
            left = 0; right = 1;
            que[0] = { tx, ty };
            memset(visited, 0, sizeof(visited));
            total += depth;
            depth = 0;//초기화
            if (++count == level) {//레벨 업
                ++level;
                count = 0;
            }
        }
    }
    printf("%hd", total);
}
/*
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
*/