[C] 7576: 토마토

일단 BFS를 이용하여 초기의 있던 토마토마다 BFS 알고리즘을 이용하여 각 그래프의 점에서

언제가 토마토가 가장 빨리 익는지를 비교하여 배열에 저장하고

마지막에 최댓값을 구하는 방식으로 코드를 짰다.

 

그렇게 하기 위해 queue_day라는 배열을 생성하여 하루가 지날때마다 하루가 추가되도록 만들었고

새로운 초기 토마토로 BFS를 탐색할 때마다 공통으로 쓰이는 배열들을 초기화해줬다.

또 다 익게 만들 수 없는 경우가 다 익은 경우를 구별해서 구했다.

 

그래서 그 결과!! 테스트 케이스는 다 맞는데 시간초과가 나오게 됐다..

#include <stdio.h>

int arr[1001][1001];
int visit[1001][1001];
int queue[1001][2];
int queue_day[1001];

int x_coordinate[4]={0,0,1,-1}; //아래로, 위로 ,오른쪽으로, 왼쪽으로
int y_coordinate[4]={1,-1,0,0};

//int tomato_day=1;

void clear_visit()
{
  for(int i=0;i<1001;i++)
    {
      queue[i][0]=0;
      queue[i][1]=0;
      queue_day[i]=0;
      for(int j=0;j<1001;j++)
        visit[i][j]=0;
    }
  
}
 
int bfs(int x_max,int y_max,int y,int x)
{
  int cnt=1;
  int tomato_day=1;
  int front=1,rear=1;
  queue[front][0]=x;
  queue[front][1]=y;
  rear++;
  
  while(front<rear)
    {
      x=queue[front][0];
      y=queue[front][1];
      for(int i=0;i<4;i++)
        {
          int nx=x+x_coordinate[i];
          int ny=y+y_coordinate[i];

          //그래프를 벗어남
          if(nx>x_max||ny>y_max||nx<1||ny<1) 
            continue;
          
         //토마토가 없는 공간          
          if(arr[ny][nx]==-1) 
          {
            if(visit[ny][nx]==0)
            {
              visit[ny][nx]=1; //지나긴 함
              cnt++;
            }            
            continue;
          }

          //초기 토마토가 있던 공간
          if(arr[ny][nx]==1 &&visit[ny][nx]==0)
          {
            visit[ny][nx]=1;
            cnt++;
          }
            
          //아직 한번도 도달하지 않고, 초기 토마토가 아닌 나머지 토마토일때(-1일때는 들어올  일이 ㅇ벗음) 
          if(visit[ny][nx]==0 && arr[ny][nx]!=1) 
          {
            visit[ny][nx]=1;
            cnt++;
            queue_day[rear]=tomato_day+1;
            queue[rear][0]=nx;
            queue[rear][1]=ny;
            rear++;
            if(arr[ny][nx]==0) //여러 태스트케이스 중 한번도 안지나간 경우
              arr[ny][nx]=tomato_day+1;
            if(arr[ny][nx]>tomato_day+1 )
              arr[ny][nx]=tomato_day+1; // 토마토가 익는데 걸리는 일수를 구함
          }
        }// for문 끝남
      
      front++;
      
      if(cnt==x_max*y_max)
      {
         
        return 0; // 다 익게 할 수있움      
      }
        
      tomato_day=queue_day[front]; //이렇게 해야 며칠째에 토마토가 익었는지 확인할 수 있음
    } //while문 끝남
  
  if(cnt!=x_max*y_max) //다 익게 할 수가 없음
    return -1;
  
}

  int main(void)
  {
     int x,y;
    scanf("%d %d",&x,&y);
    for(int j=1;j<=y;j++) //그래프 저장
      {
        for(int i=1;i<=x;i++)
          {
            scanf("%d",&arr[j][i]);
          }
      }

    int not_good;
    for(int j=1;j<=y;j++)
      {
        for(int i=1;i<=x;i++)
          {
            if(arr[j][i]==1&& visit[j][i]==0) //초기 토마토의 위치
            {
              queue_day[1]=1;
               //익은 토마토의 개수
              visit[j][i]=1; //지나갔다!
              not_good=bfs(x,y,j,i);
              clear_visit();
            }
          }
      }

    /*for(int j=1;j<=y;j++)
      {
        for(int i=1;i<=x;i++)
          {
            printf("%d ",arr[j][i]);
          }
        printf("\n");
      }*/
    
    if(not_good==-1) //다 못익거나 익어있음
    {
      int cnt=1;
      for(int j=1;j<=y;j++)
        {
          for(int i=1;i<=x;i++)
            {
              if(arr[j][i]==0) //절대 다 못익음
              {
                printf("-1");
                return 0;
              }
            }
        }
      printf("0"); //이미 다 익어있음
    }
      
   
    else //최댓값을 찾아야함
    {
      int max=0;
      for(int j=1;j<=y;j++)
        {
          for(int i=1;i<=x;i++)
            {
              max=arr[j][i]>max?arr[j][i]:max;
            }
        }
      printf("%d",max-1); //구현자체를 tomato_day를 하루 더 추가해서 했기 때문에 최댓값에서 -1 빼줘야함
    }
      
  }

 

그래서 생각을 바꿔서..

처음에 위와 같이 한 이유가 main 함수에서 for문을 통해 bfs를 호출할 때 딱 그 순간만 dfs처럼 작동하기 때문에

각각의 처음 토마토 위치마다 bfs를 호출해서 비교했었다.

 

생각을 해보니 그냥 처음에 초기 토마토들을 queue배열에 넣으면 됐다..

어차피 전역이라서 그냥 넣으면 될 것을....

 

그리고 시간초과가 1%에서 계속해서 '틀렸습니다'가 나왔는데

queue와 queue_day의 size를 10000001로 했더니 해결되었다.

queue에 들어갈 수 있는 범위 자체가 최소 1000*1000이기 때문에 이것보다 커야 한다.

 

#include <stdio.h>

int arr[1001][1001];
int visit[1001][1001];
int queue[10000001][2];
int queue_day[10000001];

int front=1,rear=1;

int x_coordinate[4]={0,0,1,-1}; //아래로, 위로 ,오른쪽으로, 왼쪽으로
int y_coordinate[4]={1,-1,0,0};

//int tomato_day=1;

 
int bfs(int x_max,int y_max,int cnt)
{
  
  int tomato_day=0;
    
  while(front<rear)
    {
      int x=queue[front][0];
      int y=queue[front][1];
      for(int i=0;i<4;i++)
        {
          int nx=x+x_coordinate[i];
          int ny=y+y_coordinate[i];

          //그래프를 벗어남
          if(nx>x_max||ny>y_max||nx<1||ny<1) 
            continue;
          
         //토마토가 없는 공간          
          if(arr[ny][nx]==-1) 
          {       
            continue;
          }

          //초기 토마토가 있던 공간은 이미 지나감        
            
          //아직 한번도 도달하지 않았을 때
          if(visit[ny][nx]==0) 
          {
            visit[ny][nx]=1;
            cnt++;
            queue_day[rear]=tomato_day+1;
            queue[rear][0]=nx;
            queue[rear][1]=ny;
            rear++;
            arr[ny][nx]=tomato_day+1;            
          }
          
        }// for문 끝남
      front++;      
      if(cnt==x_max*y_max)
      {
         return 0; // 다 익게 할 수있움      
      }        
      tomato_day=queue_day[front]; //이렇게 해야 며칠째에 토마토가 익었는지 확인할 수 있음
    } //while문 끝남
  
  if(cnt!=x_max*y_max) //다 익게 할 수가 없음
  {
    
    return -1;
  }
    
  
}

  int main(void)
  {
     int x,y;
    scanf("%d %d",&x,&y);
    for(int j=1;j<=y;j++) //그래프 저장
      {
        for(int i=1;i<=x;i++)
          {
            scanf("%d",&arr[j][i]);
          }
      }

    int not_good,cnt1=0,cnt2=0;
    for(int j=1;j<=y;j++)
      {
        for(int i=1;i<=x;i++)
          {
            if(arr[j][i]==-1)
            {
              visit[j][i]=1;
              cnt1++;
            }
              
            if(arr[j][i]==1&& visit[j][i]==0) //초기 토마토의 위치
            {
              queue[rear][0]=i;
              queue[rear][1]=j;
              queue_day[1]=1;
              rear++;
              cnt2++;
               //익은 토마토의 개수
              visit[j][i]=1; //지나갔다!             
            }
          }
      }
    if(cnt1+cnt2==x*y) //이미 다 익어있음
    {
      printf("0");
      return 0;
    }
    not_good=bfs(x,y,cnt1+cnt2);

    /*for(int j=1;j<=y;j++)
      {
        for(int i=1;i<=x;i++)
          {
            printf("%d ",arr[j][i]);
          }
        printf("\n");
      }*/
    
    if(not_good==-1) //다 못익음
    {      
      printf("-1");      
    }      
   
    else //최댓값을 찾아야함
    {
      int max=0;
      for(int j=1;j<=y;j++)
        {
          for(int i=1;i<=x;i++)
            {
              max=arr[j][i]>max?arr[j][i]:max;
            }
        }      
      printf("%d",max);
    }
      
  }