[BOJ/7576번토마토] c++ / BFS

문제

상자 안에 있는 토마토가 모두 익을 때까지의 최소 날짜를 구하는 문제

-익은 토마토는 1, 익지 않은 토마토는 0, 토마토가 없는 칸은 -1로 표시됨

 

생각

상자 안에 토마토가 한개만 있으면 문제가 단순한데,

두개 이상이 있을 경우엔 토마토가 동시에 익으니까 이걸 어떻게 풀어야 하나 고민을 했음

처음에 토마토가 있는 칸을 찾아서 몽땅 큐에 넣으면 되겠다는 생각은 했음

날짜 세는건 이전에 풀었던 백준 2178번 문제와 같아서 구현은 쉬웠음

근데 생각은 되는데 코드를 짜려니까 모르겠어서 바킹독님 강의 들음

 

문제풀이

1. board에서 토마토가 들어있는 칸을 큐에 모두 집어넣음

-동시에 토마토가 익을 수 있음

2. 1번 과정에서 익지 않은 토마토 칸이 나오면 -1 표시해줌 ( 나중에 토마토가 모두 익었는지 확인하기 위함 )

3. 반복문 사용해서 익은 토마토 기준으로 상하 좌우에 익지 않은 토마토가 있는지 확인 ( 코드에선 day칸이 0인지 확인했음 )

4. 안 익은 토마토의 day칸에는 기준이 되었던 토마토의 day칸 값에서 1을 더해준 값을 저장함

5. day 칸에 -1이 있으면 토마토가 익지 않은 것임 \ 다 익었으면 day칸에서 최댓값을 찾아 출력하면 됨

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[1001][1001];
int day[1001][1001];
int M, N, ans;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> M >> N;
    queue<pair<int, int>> Q;

    for ( int i = 0; i < N; i++ ) 
        for ( int j = 0; j < M; j++ )
            cin >> board[i][j];

    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 1 )
                Q.push({i, j}); // 익은 토마토 몽땅 넣기
            else if ( board[i][j] == 0 )
                day[i][j] = -1; // 안 익은 토마토 표시 해주기
        }

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        for ( int dir = 0; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( day[nx][ny] >= 0 ) continue;
            day[nx][ny] = day[cur.X][cur.Y] + 1; // 이것도 포인트
            Q.push({nx, ny});        
        }
    }

    
 
    for ( int i = 0; i < N; i++ ){
        for ( int j = 0; j < M; j++ ) {
            if ( day[i][j] == -1 ) {
                cout << -1;
                return 0;
            }
            ans = max(ans, day[i][j]);
        }
    }
    cout << ans;
   
}