7576번 토마토 - C++

✅️[문제]
https://www.acmicpc.net/problem/7576

7576번: 토마토

✅️[풀이]

❗️(m,n) 에서 좌표중 값이 1인 것을 큐에 넣는다!
BFS를 돌려서, 이동 가능한 좌표에 이전 좌표의 값 + 1을 해주는 방식이다.
(m,n)에 대해 좌표값중 0이 있으면 불가능으로 판단하고, 0이 없는 경우 각 좌표의 최댓값을 출력하면 된다!

✅️[코드]

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

int dx[4] = {1,0,-1,0};

int dy[4] = {0,1,0,-1};

int board[1002][1002];

bool vis[1002][1002];

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    

    int m,n;

    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];

            if(board[i][j] == 1) {

                Q.push({i,j});

                vis[i][j] =1;

            }

        }

    }

    while(!Q.empty()){

        pair<int,int> q2 = Q.front(); Q.pop();

        for(int i=0; i<4; i++){

            int x = q2.X + dx[i];

            int y = q2.Y + dy[i];

            

            if(x<0 || x>=n || y<0 || y>=m) continue;

            if(board[x][y] == -1 || vis[x][y]) continue;

            board[x][y] = board[q2.X][q2.Y] + 1;

            vis[x][y] = 1;

            Q.push({x,y});

        }

    }

    int mx = 0;

    for(int i=0; i<n; i++){

        for(int j=0; j<m; j++){

            if(board[i][j] == 0) {

                cout << -1;

                return 0;

            }

            mx = max(mx, board[i][j]);

        }

    }

    cout << mx -1;

    

}

✅️[소감]
🍅🍅🍅
이 문제는 BFS중 쉬운 문제 인것 같다!
이번주 내로 BFS 정복하기!