[백준 7576] 토마토 [C]

백준 - 7576

---

풀이

"백준 2178, 미로 탐색"과 풀이가 비슷하다. 단, 시작점이 여러개이다.

토마토의 여부를 입력받을 때, 익지않은 토마토의 개수와 익은 토마토의 개수를 미리 계산했다.

익지않은 토마토를 발견할 때마다 empty를 하나씩 감소하며, 탐색이 끝난 후 empty가 0보다 크면 모든 토마토가 익을 수 없는 상황이기 때문에 -1을 반환했다.

#include <stdio.h>
#define MAX 1001
int box[MAX][MAX], M, N, rear;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
typedef struct{
    int x, y;
}Queue;
Queue q[MAX*MAX];
void push(int i, int j){
    q[rear].x = i;
    q[rear++].y = j;
}
int bfs(int empty){
    if (!empty) return 0;
    int x, y, px, py, front = 0;
    while (front != rear){
        x = q[front].x;
        y = q[front++].y;
        for (int i = 0; i < 4; i++){
            int tx = x+dx[i], ty = y+dy[i];
            if (tx > 0 && ty > 0 && tx <= N && ty <= M)
                if (!box[tx][ty]){
                    box[tx][ty] = box[x][y] + 1;
                    push(tx, ty);
                    empty--;
                    px = tx, py = ty;
                }			
        }
    }
    return empty > 0 ? -1 : box[px][py]-1;
}
int main(){
    int empty = 0;
    scanf("%d %d", &M, &N);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++){
            scanf("%d", &box[i][j]);
            if (!box[i][j]) empty++;
            else if (box[i][j] == 1) push(i, j);
        }		
    printf("%d", bfs(empty));
}

---

출처 및 참고자료

7576번: 토마토

[백준 2178] 미로 탐색 [C]