[C언어] 7576번 토마토 - 그래프 이론, BFS

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 006000

typedef struct Co {  //좌표를 영어로 하면 coordinate
    int x;
    int y;
    int day;
} Co;

typedef struct Queue {  //큐 구현
    int start;
    int rear;
    Co data[MAX_QUEUE_SIZE]; 
} Queue;

int a[4] = {1, 0, -1, 0};  //상하좌우
int b[4] = {0, -1, 0, 1};

void enqueue(Queue *q, Co c)
{
    q->rear = (q->rear+1)%MAX_QUEUE_SIZE;
    q->data[q->rear]=c;
}

Co dequeue(Queue *q)
{
    q->start=(q->start+1)%MAX_QUEUE_SIZE;
    return q->data[q->start];
}

int Emt_Queue(Queue *q)
{
    if(q->rear == q->start)
        return 1;
    else
        return 0;
}

int main()
{
    int M, N;  //상자의 크기
    int arr[1002][1002]={};
    int i, j;
    
    Queue q = {0};  //큐 초기화
    Co co, sp;  //좌표: coordinate, 예비: spare
    
    scanf("%d %d", &N, &M);

    int flag=1;
    for(i=1; i<=M; i++) {  //상자 상태
        for(j=1; j<=N; j++) {
            scanf("%d", &arr[i][j]);
            
            if(arr[i][j]==1) {  //좌표 입력받아 큐에 저장
                co.x=i, co.y=j, co.day=0;
                enqueue(&q, co);
            }
            else
                flag=0;
        }
    }
    
    while(!Emt_Queue(&q)) {
        co = dequeue(&q);
        for(i=0; i<4; i++) {
            if(co.x+a[i]>=1 && co.x+a[i]<=M && co.y+b[i]>=1 && co.y+b[i]<=N && !arr[co.x+a[i]][co.y+b[i]]) {  //상하좌우 탐색중
                arr[co.x+a[i]][co.y+b[i]]=1;
                sp.x=co.x+a[i], sp.y=co.y+b[i], sp.day = co.day+1;  //날짜를 1 더하기
                enqueue(&q, sp);
            }
        }
    }
    
    if(flag)  //모두다 익었다면
        printf("0");
    else {
        int all=0;
        
        for(i=1; i<=M; i++) {
            for(j=1; j<=N; j++) {
                if(!arr[i][j])
                    all=1;
                
            }
        }
        
        if(all)
            printf("-1");
        else
            printf("%d", sp.day);
    }
    
    return 0;
}

 

알고리즘은 나름 간단했다. 그냥 큐에 새로 탐색한 것을 위에 올리고 아래것을 꺼내는 거다. 넣을 때 날짜를 같이 넣음으로써 새로 익은 것을 다음 날짜로 기록해서 총 걸리는 날자를 알 수 있다. 큐를 다 꺼내서 비었는데 익지 않은 것이 있다면 애초부터 익을 수 없는 것이란 것을 알 수 있다. 예상은 했지만 큐가 500000개나 되도 다찰 줄은 몰랐다. 이것 때문에 30분 정더 고민했던 것 같다. 왜 안되는지

 

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.