[백준 7576 c++ VOO] 토마토

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // memset 헤더
#include <queue>
using namespace std;
// [백준 7576 c++ VOO] 토마토 
// 문제: 이차원 그래프에 주어진 토마토가 모드 익는데 걸리는 최소일 수 구하기
// 접근: 이차원 그래프 최소일수 -> bfs
// 이동시간를 저장하는 dist배열 따로 저장
// 처음 시작하는 위치를 모두 추출한 다음 bfs 시작하는게 특징
// 시간복잡도: ??
// 풀이 :
// 그래프 입력
// 익은 토마토의 위치 큐에 모두 삽입
// 익은 토마토의 큐를 이용해서 bfs 탐색
// 탐색하며 걸린 일 수 저장
// 탐색이 끝난 후 안익은 토마토가 있으면 -1출력
// 아니면 토마토가 익는데 걸린 시간출력
#define MAX 1001
int m, n;
int gr[MAX][MAX];
bool visit[MAX][MAX];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int dist[MAX][MAX];
queue<pair<int, int>> q;
 
void bfs() {
    
    int r, c;
    while (!q.empty()) {
        r = q.front().first;
        c = q.front().second;
        q.pop();
 
        // 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];
 
            if (nr<1 || nr>n || nc<1 || nc>m) { continue; } // 범위 검사
            if (!visit[nr][nc] && gr[nr][nc] == 0) { // 방문, 토마토 검사
                q.push({ nr,nc }); visit[nr][nc] = 1;
                dist[nr][nc] = dist[r][c] + 1; // 이동거리
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); // 계산시간 단축 // cin,scanf 같이 쓰면 오류
    cin.tie(nullptr); cout.tie(nullptr);// 입출력 시간 단축 // 이것을 쓰면 scanf,printf섞어 쓰면 안됨
    //그래프 입력
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> gr[i][j];
            if (gr[i][j] == 1) { q.push({ i,j }); visit[i][j] = 1; } // 익은 토마토 미리 큐에 푸쉬, 방문
        }
    }
    // 탐색
    bfs();
 
    // 최소일수, 불가능 예외 검사
    int maxN = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!visit[i][j] && gr[i][j] == 0) { cout << -1 << '\n'; return 0; }
            maxN = max(maxN, dist[i][j]);
        }
    }
    cout << maxN << '\n';
    return 0;
}