백준 7576:토마토

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

백준 7576번 토마토 문제입니다. 이번문제는 DFS로는 접근하기 어려운 문제인 것 같아요. 혹시 DFS로 푸신분이 있으시다면 댓글로.. 알려주세요! 이번문제도 다른 탐색문제들과 다른것은 많이 없습니다. -1이 탐색 불가능한점(바다문제라면 바다에 해당되겠네요)으로 설정 후 탐색해 주시면 됩니다. 또한 다른 문제들은 시작점이 하나지만 이문제는 시작점이 여러개가 될 수 있는 문제입니다. 따라서 큐에 시작점을 삽입할때 1로 표시된 시작점들을 모두 넣어주어야 해요!! 그럼 컴퓨터가 알아서.. 다해줍니다^^.

밑에는 제 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int r[4] = { 0,-1,0,1 };
int c[4] = { -1,0,1,0 };
 
typedef struct rc {
    int r;
    int c;
}pos;
 
int N, M, Count;
 
vector<vector<int> > tomato;
 
bool isSafe(pos p) {
    if (p.r<0 || p.r>N - 1 || p.c<0 || p.c>M - 1) return false;
    else return true;//범위 벗어나는지 체크
}
 
void bfs(vector<pos>& start) {
    queue<pos> q;
    for (int i = 0; i < start.size(); i++) {
        q.push(start[i]);//시작점을 모두 큐에 삽입
    }
    while (!q.empty()) {
        pos cur = q.front();
        for (int i = 0; i < 4; i++) {//탐색
            pos next = { cur.r + r[i],cur.c + c[i] };
            if (isSafe(next) && !tomato[next.r][next.c]) {
                q.push(next);//조건에 맞으면 큐에 삽입
                tomato[next.r][next.c] = tomato[cur.r][cur.c] + 1;
            }
        }
        q.pop();
    }
}
 
int check() {
    int max = 1;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (tomato[r][c] == 0) {
                return -1;//익지 않은 토마토 발견시 -1리턴
            }
            else if (tomato[r][c] > max) {
                max = tomato[r][c];//최댓값 찾기
            }
        }
    }
    return max;
}
 
int main(void) {
    cin >> M >> N; vector<pos> start; pos s;
    tomato.resize(N);
    for (int r = 0; r < N; r++) {
        tomato[r].resize(M);
        for (int c = 0; c < M; c++) {
            cin >> tomato[r][c];
            if (tomato[r][c] == 1) {//1이라면
                s.r = r; s.c = c;//시작점에 저장
                start.push_back(s);
            }
        }
    }
 
    bfs(start);//탐색 후
 
    int cnt = check();//몇 일 걸리는지
    if (cnt == -1) cout << "-1" << endl;
    else cout << cnt - 1 << endl;
 
    return 0;
}