백준(C++) 7567 [토마토]

 

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

토마토 7567

접근방법

전에 풀었던 문제와 같이 BFS를 이용하여 푸는 문제이다. 차이점이 있다면 시작점이 여러개라는 점이다.

그렇다면 그래프 배열 입력시 시작점을 전부 큐에 넣어주면 된다.

다른 점이 있다면, 이 문제에서 토마토는 동시에 인근 토마토를 익게 하므로 순서를 
시작 토마토 -> 시작 토마토에 익은 토마토-> 익은 토마토에 익은 토마토 ->... 가 되어야한다.

그래서 익어야되는 토마토와 몇일이 지난뒤 익은 토마토가 되는지 정보를 적어놔야한다.

익어야되는 토마토를 없애면서,  익은 날짜를 적기위해 방문 배열에 이것들을 적기로 했다.

BFS를 돌린후 그래프 배열을 전부 돌아 안익은 토마토를 확인하고

몇일이 지나면 모두 익는지 일수를 구하면된다. BFS가 최종값이 최소가 되므로 익은 날짜가 가장 큰

날을 출력하면된다.

 

다음은 코드이다. 

#include<iostream>
#include<queue>

using namespace std;
    int board[1005][1005];
    int is[1005][1005];
    int xx,yy;
    int ans; 
    int x[4] = {1 ,0 ,-1, 0};
    int y[4] = {0 ,1 , 0 ,-1};
    

    int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> yy >> xx;
    
    queue<pair<int, int> > q;
        
    for(int a=0;a<xx;a++){
        for(int b=0;b<yy;b++){
            cin >> board[a][b];
            if(board[a][b] == 1)
            q.push({a,b}); // 시작점
            if(board[a][b] == 0)
             is[a][b] = -1 ; // 채워야되는 것
             }
              }

               
                
            while(!q.empty()){
                auto cur = q.front();q.pop();
                for(int dir =0; dir < 4;dir++){
                    int nx = cur.first+x[dir];
                    int ny = cur.second+y[dir];
                    if(nx < 0 || nx >=xx || ny < 0 || ny >= yy) continue; //범위 벗어남
                    if(is[nx][ny] != -1 ) continue; // -1,1 일때 
                    is[nx][ny] = is[cur.first][cur.second]+1; // 거리 + 1
                    q.push({nx,ny});
                   
                   
                }
            }

    for(int a=0;a<xx;a++){
        for(int b=0;b<yy;b++){
            if(is[a][b] == -1){
            cout << -1 ; 
            return 0;
            }

    ans=max(ans,is[a][b]);
        }
            }
    cout << ans <<'\n';

        }

번외로 7569 3차원 토마토도 있다. 이는 같이 규칙에 3차원으로 변한거 뿐이다. 이동방향을 상하좌우 에서

상하좌우+해당좌표의 아래 차원 +해당좌표의 위 차원 만 추가하면된다.