백준 16236: 아기 상어 [C언어], 삼성 코딩 테스트

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct{
    int y, x, d;
}queue;
int NN;
queue Q[100000];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
int map[22][22];
int visited[22][22];
int target[100000][3]; int t;
int babyfish = 2; // 아기상어의 기
int by, bx, res, fishcount; // 아기 상어의 좌표와 먹은 물고기의 수
void input();
int solve();
void bfs(int y, int x);
int main(){
    input(); // 입력
    printf("%d", solve());
    return 0;
}
 
void input() { // 입력
    scanf("%d", &NN); 
    for (int i = 1; i <= NN; i++) {
        for (int j = 1; j <= NN; j++) {
            scanf("%d", map[i] + j);
            if (map[i][j] == 9) {
                by = i; bx = j; map[i][j] = 0; // 아기 상어의 좌표를 저장하고 그 부분은 지나갈 수 있게 비워준다
            }
        }
    }
}
int solve() {
    while(1){
        bfs(by, bx);
        if (t == 0) break;
        else {
            int miny = 22, minx = 22;
            for(int i = 0; i < t; i++) if (target[i][0] < miny) miny = target[i][0];
            for(int i = 0; i < t; i++) if (target[i][0] == miny and target[i][1] < minx) minx = target[i][1];
            for(int i = 0; i < t; i++) if (target[i][0] == miny and target[i][1] == minx) {
                by = target[i][0]; bx = target[i][1]; res += target[i][2]; map[by][bx] = 0; break;
            }
            t = 0;
            fishcount++;
            if (fishcount == babyfish) {
                fishcount = 0; babyfish++;
            }
        }
        for(int i = 1; i <= NN; i++) for(int j = 1; j <= NN; j++) visited[i][j] = 0;
    }
    return res;
}
void bfs(int y, int x) {
    int front, rear, qy = y, qx = x, qd = 0, distance = 100000;
    front = -1; rear = -1;
    Q[++rear].y = qy; Q[rear].x = qx; Q[rear].d = qd;
    visited[qy][qx] = 1;
    while(front != rear) {
        qy = Q[++front].y; qx = Q[front].x; qd = Q[front].d;
        for(int i = 0; i < 4; i++) {
            if (qy + dy[i] < 1 or qy + dy[i] > NN or qx + dx[i] < 1 or qx + dx[i] > NN) continue;
            if (qd + 1 > distance) continue;
            if (visited[qy + dy[i]][qx + dx[i]]) continue;
            if (map[qy + dy[i]][qx + dx[i]] > babyfish) continue;
            if (map[qy + dy[i]][qx + dx[i]] != 0 and map[qy + dy[i]][qx + dx[i]] < babyfish) {
                target[t][0] = qy + dy[i]; target[t][1] = qx + dx[i]; target[t++][2] = qd + 1; distance = qd + 1;
            }
            visited[qy + dy[i]][qx + dx[i]] = 1;
            Q[++rear].y = qy + dy[i]; Q[rear].x = qx + dx[i]; Q[rear].d = qd + 1;
        }
    }
}