[백준] 16236 아기 상어

복기

처음엔 단순히 완전탐색 문제군 하고 시작했다가 몇 번이나 생각을 잘못해서 디버깅에 시간을 많이 허비했던 문제입니다. 그래도 다행히 잘못 생각한 부분들을 예제 입출력에서 다 잡아줘서 풀 수 있었네요. ㅋㅋ 처음 잘못 생각했던 건(사실 별 생각이 없었다는게 더 맞는 것 같지만) 동일한 거리의 물고기가 있을 때 먹을 물고기의 우선 순위(1번: 위에 있는 물고기, 2번: 왼쪽에 있는 물고기) 구현을 단순히 탐색 방향을 위, 왼쪽, 오른쪽, 아래 로 해놓고 됐다고 생각했던 건데요. 4번 예제에서 걸려서 디버깅 하다보니 중간에 잘못된 물고기를 먹더군요. 다시 생각해보니 아래 그림처럼 6번이 5번보다 위에 있어 우선 순위가 높지만 Queue엔 더 늦게 들어간다는걸 깨달았습니다.

두 번째 잘못 생각한 건 거리를 그냥 두 지점간 최단 거리로 구한건데 이러면 돌아가는 경우를 전혀 고려하지 않은게되죠. 변명을 해보자면...... 이때 많이 졸렸나봐요. 아래는 코드입니다.

#pragma warning(disable : 4996)
#include <stdio.h>
typedef struct _queue {
    int d[405][2];
    int f, r;
} Queue;
int N, M, sx, sy, ss, sc, ans;
int in[22][22], d[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
bool vis[22][22];
Queue q1, q2, q3;

void enqueue(Queue* q, int x, int y) {
    q->d[q->r][0] = x;
    q->d[q->r][1] = y;
    (q->r)++;
}
void dequeue(Queue* q, int* px, int* py) {
    *px = q->d[q->f][0];
    *py = q->d[q->f][1];
    (q->f)++;
}
bool isEmpty(Queue* q) {
    return q->f == q->r;
}
void clear(Queue* q) {
    q->f = q->r = 0;
}
void solve(void) {
    Queue *cur = &q1;
    Queue *next = &q2;
    enqueue(cur, sx, sy);
    vis[sx][sy] = true;
    
    int dis = 0;
    while (M > 0 && !isEmpty(cur)) {
        while (!isEmpty(cur)) {
            int x, y, xx, yy;
            dequeue(cur, &x, &y);
            for (int i = 0; i < 4; i++) {
                xx = x + d[i][0];
                yy = y + d[i][1];
                if (xx < 1 || N < xx || yy < 1 || N < yy || vis[xx][yy]) continue;
                if (in[xx][yy] > ss) continue;
                
                vis[xx][yy] = true;
                if (in[xx][yy] == 0 || in[xx][yy] == ss)
                    enqueue(next, xx, yy);
                else
                    enqueue(&q3, xx, yy);
            }
        }
        dis++;
        if (isEmpty(&q3)) {
            Queue* tmp = cur;
            cur = next;
            next = tmp;
            clear(next);
        }
        else {
            int x, y, xx, yy;
            dequeue(&q3, &x, &y);
            while (!isEmpty(&q3)) {
                dequeue(&q3, &xx, &yy);
                if (x > xx || (x == xx && y > yy))
                    x = xx, y = yy;
            }
            clear(cur);
            clear(next);
            clear(&q3);
            enqueue(cur, x, y);
            in[x][y] = 0;
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    vis[i][j] = false;
            vis[x][y] = true;
            ans += dis;
            dis = 0;
            sx = x, sy = y;
            sc--;
            if (sc == 0)
                ss = sc = ss + 1;
            M--;
        }
    }
}

int main(void) {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) {
            scanf("%d", &in[i][j]);
            if (in[i][j] == 9) {
                sx = i;
                sy = j;
                ss = sc = 2;
                in[i][j] = 0;
            }
            else if (in[i][j]) {
                M++;
            }
        }
    solve();
    printf("%d\n", ans);
    return 0;
}

N의 최댓값이 20이라 대충 계산해서 물고기 찾는데 맵 다뒤져도 400, 물고기가 있어봐야 400마리, 합쳐도 160K 번 밖에 안되서 일단 마음은 편했습니다. 코드가 좀 지저분하지만 설명을 해보자면 우선 아기상어는 입력받을 때 맵에서 때어내서 변수 sx, sy, ss, sc 에 넣어 두었습니다. (변수명이 abc라 부연설명을 붙히자면 앞에 s는 shark, 뒤의 s는 size, c는 count) 맵안의 물고기 갯수는 변수 M에 저장해두었고요. solve() 함수를 보면 구현 방법은 BFS입니다. 큰 while문 안에 작은 while문 하나와 if else문 하나가 들어있습니다. 큰 while문은 먹을 물고기가 있고 이동이 가능한 상태면 계속 돕니다. 작은 while문은 실제 이동을 하는 부분입니다. step-by-step으로 이동하기위해 큐를 하나 더 사용했습니다. 이번 턴에 움직일 위치는 cur 큐에 들어있고 다음 이동할 위치는 next라는 다른 큐에 넣었습니다. 또, 이동중에 먹을 수 있는 물고기를 발견하면 그 물고기는 q3이라는 또다른 큐에 넣었습니다. 이번 턴의 이동을 마치면(작은 while문이 끝나면) if else문에서 먹을 수 있는 물고기를 발견했는지? 못했는지? 확인합니다. 발견 못했으면 next큐에 들어있는 좌표들이 새로운 턴에서 이동을 시작할 위치가 되기 때문에 cur큐와 next큐를 서로 바꿉니다. 발견했다면 q3안에 있는 물고기중 가장 우선 순위가 높은 물고기를 찾아서 먹고 아기 상어의 위치를 바꾼 후 새로운 탐색을 위한 준비를 하고 시작점으로 돌아갑니다.

문제를 풀고 다른 훌륭한 분들의 코드를 보니...... 작은 while문을 시작하기 전에 cur 큐의 사이즈를 아니까 딱 그만큼만 돌리면 어차피 한 step만큼만 돌기 때문에 굳이 큐를 여러개 쓸 필요는 없었네요. 대신 나머지 연산으로 큐를 환형으로 만들고요. 먹을 물고기를 저장했던 q3도 그냥 발견할 때마다 그때그때 확인해서 가장 우선순위 높은 놈으로 들고있으면 될 것 같습니다. 허허,, 이 것으로 오늘의 복기를 마칩니다.