BOJ 7576 토마토 c++

백준 7576 토마토 문제

 

먼저 X, Y는 pair<int, int>를 위해 define 한다.

 

dx[n] + dy[n] 는 항상 상, 하, 좌, 우 중 하나를 나타낸다.

 

토마토가 배치된 맵을 담을 board 2차원 배열을 선언하고,

또 거리를 나타낼 dist 2차원 배열을 선언한다.

main함수에서는 먼저 board에 값을 채워넣는다. 안 익은 토마토만 넣고, 익은 토마토는 큐에 넣는다.

 

while Q가 비지 않을 때까지 반복하는데,

cur에는 Q의 맨 첫 번째 pair를 담는다.

 

nx, ny는 현재 위치의 상, 하, 좌, 우를 반영한 값이다.

그 상하좌우 좌표에 대해 범위를 벗어난 경우와 이미 방문한 경우는 모두 continue 해버리고,

그렇지 않은 경우에 대해 dist[nx][ny]에 현재좌표, 즉 dist[cur.X][cur.Y] + 1을 해준다.

 

마지막으로 dist배열에 -1이 남아있는 경우, 즉 익지 않은 토마토가 남아 있는 경우 -1을 출력하고,

그런 경우가 없을 때에는 dist배열 중 가장 큰 값이 들어있는 칸의 값을 출력한다.

#include <bits/stdc++.h>
using namespace std;
# define X first
# define Y second
int n;
int m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int board[1002][1002];
int dist[1002][1002];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    queue<pair<int, int>> Q;
    /*board에 채워넣기*/
    int i, j;
    for (i = 0; i < n; i++){
        for (j = 0; j < m; j++){
            cin >> board[i][j];
            if (board[i][j] == 1)
                Q.push({i, j});
            if (board[i][j] == 0)
                dist[i][j] = -1; 
        }
    }
    int nx;
    int ny;
    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            nx = cur.X + dx[dir];
            ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (dist[nx][ny] >= 0)
                continue;
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            Q.push({nx, ny});
        }
    }
    int ans = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (dist[i][j] == -1) {
                cout << -1;
                return 0;
            }
            ans = max(dist[i][j], ans);
        }
    }
    cout << ans;
}