[백준] 7576 토마토 BFS

문제 :

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

7576번: 토마토

 

분석 :

이런식으로 토마토 농장이 존재 할때 

1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸

을 의미한다.

 

익은 토마토 중심으로 상하좌우로 하루마다 토마토가 익는데 몇일이면 농장 내 모든 토마토가 익는지 날짜를 출력하는 문제였다.

 

우선 토마토 농장을 탐색한다는 점에서 BFS, DFS로 접근해야 한다 생각했고 탐색을 하면서 방문하지 않았던  0을 for문을 돌면서 1씩 늘려 주고 모든 0이 1로 바뀌었을때 dfs 탐색을 통해 날짜를 계산하도록 하였다. 

 

//
//  7576_tomato.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/22.
//

#include <stdio.h>
#include <queue>
#include <iostream>

using namespace std;
int tomatoMap[1001][1001];
int M, N;
int tomatoCount;
int dfscount;
int visit[1001][1001] = {false, };

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

queue<pair<int, int>> s;

void tomato_dfs(){
    while(!s.empty()){
        pair<int, int> cur = s.front();
        s.pop();
       
        for(int i = 0; i < 4; i++){
            int nextX = cur.first + dx[i];
            int nextY = cur.second + dy[i];
           
            if(nextX < N && nextY < M && nextX >= 0 && nextY >= 0 ){
                if(visit[nextX][nextY] == false && tomatoMap[nextX][nextY] == 0){
                    visit[nextX][nextY] = true;
                    s.push({nextX, nextY});
                    dfscount++;
                    tomatoMap[nextX][nextY] = tomatoMap[cur.first][cur.second] + 1;
                }
            }
        }

    }
}

int main(){
    cin >> M >> N; // 6 4
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> tomatoMap[i][j];
            if(tomatoMap[i][j] == 0){ // tomato count
                tomatoCount++;
            }else if(tomatoMap[i][j] == 1){
                s.push({i,j});
                //startPoint = make_pair(i,j);
            }
        }
    }
    int max = 0;
    if(tomatoCount == 0){
        cout << "0" << '\n'; // 모든 토마토 익어있는 상태
        return 0;
    }else{
        tomato_dfs();
        if(tomatoCount - dfscount != 0){ // 토마토 다 익지 x
            cout << "-1" << '\n';
            return 0;
        }
        for(int i = 0; i < N; i++){ // 토마토 다 익힘
            for(int j = 0; j < M; j++){
                if(max < tomatoMap[i][j]){
                    max = tomatoMap[i][j];
                }
                    
            }
        }
        cout << max - 1 << '\n';

    }
    return 0;
}

마지막 토마토 익은 날짜를 구하기 위해 이중 for문으로 max 값을 찾는 부분이 비효율적으로 보인다. 이부분은 수정해보아야겠다.