7576_토마토

토마토 케이스..!

처음에 DFS 로 풀려고 했는데 dfs 로 풀면 모든 정점을 다 돌 수가 없기 때문에 시간초과가가 났고...

정확한 기저사례, 반례를.. 잘 구하지 못해서 틀렸다..

BFS 로 다시 도전해서 풀어보기.

 

1. fist trial - dfs 로 도전해서 실패

 

#include <iostream>
using namespace std;
int N, M; //M : 가로 칸, N: 세로 칸 
int count; //최소날짜 수 
#define MAX 1000
int tomatoBox [MAX][MAX];
int checked [MAX][MAX];
int dx[] = { 0, 0, -1, 1};
int dy[] = { -1, 1, 0, 0};
void tomatoSearch(int x, int y)
{
    //bfs 로직 확인해서 
    //토마토 <-- --> 상하좌우로직 으로 익은 것 옆의 주변부도 함께 익도록 설정. 
    // 1: 익은 토마토, 0: 아직 안익은 토마토 , -1:토마토가 없음.
    //익은 토마토에 대해서만
    checked[x][y] = 1;
 
    //빠진 내용 : 기저사례
    if(tomatoBox[x][y] == -1)
        return;
 
    if(tomatoBox[x][y] == 1)
 
 
 
    if(checked[x][y] == 1 )
    {
        for(int i = 0; i< 4; i++)
        {
            int x_value = dx[i];
            int y_value = dy[i];
 
            if(checked[x + x_value][y + y_value] == 0) //여기서, x value, y value 를 더하는 것을 깜박했당.
                tomatoSearch(x_value, y_value); //주변부 영향을 받아서 익는 과정
        }
    }
    count++;
}
 
int main(void)
{
    cin>>M>>N;
    //토마노트들의 정보 input process
    for(int i =0; i<M ; i++)
        for(int j=0 ; j<N; j++)
            scanf("%d",&tomatoBox[i][j]);
 
    for(int i =0; i<M ; i++)
         for(int j=0 ; j<N; j++)
             if(tomatoBox[i][j] == 1) //익었을 경우에만 돌도록 설정.
                 tomatoSearch(i,j);
 
 
    //main process
    ////예외처리과정 : 토마토가 모두 익은 상태 : 0, 토마토가 모두 익지 못하는 상황 :-1 
    /////아예 input 부터 받아서 처리
    //<--- ---> 상하좌우를 확인하여, 옆에 있는 토마토가 있을 경우, 
 
 
    printf("%d", count);
 
    return 0;
}
 
//유용한 사이트 : https://kyunstudio.tistory.com/118
 

 

2. 2nd trial -BFS

 

[ coming sooooon]