[백준] 7576번 토마토 - C++

문제

• 백준 7576번 토마토
• https://www.acmicpc.net/problem/7576

풀이

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

map에 입력받은 배열에 1인 값을 찾아 bfs 탐색을 시작한다. 방문하지 않은 배열이고 값이 0(익지않은 토마토) 일때, 값을 1(익은 토마토)로 바꾸고 방문처리 해준 후 큐에 다음 좌표를 담고 탐색을 계속 진행한다.

코드

#include <iostream>
#include <queue>

using namespace std;

struct POS{
    int y,x,date;
};

int n,m,ans;
bool visited[1000][1000];
int map[1000][1000];
POS pos;
queue<POS> q;

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int y=0;y<m;y++){
        for(int x=0;x<n;x++){
            cin >> map[y][x];
            if(map[y][x]==1){
                pos.y=y, pos.x =x, pos.date=0;
                visited[pos.y][pos.x] = true;
                q.push(pos);
            }
        }
    }

    while(!q.empty()){
        POS cur = q.front(); q.pop();
        ans = cur.date;
        for(int k=0;k<4;k++){
            POS next;
            next.y = cur.y + dy[k];
            next.x = cur.x + dx[k];
            next.date  = cur.date + 1;

            if(next.y < 0 || next.y >= m || next.x < 0 || next.x >=n){
                continue;
            }
            if(map[next.y][next.x]==-1 || map[next.y][next.x]==1){
                continue;
            }
            if(visited[next.y][next.x]==false && map[next.y][next.x]==0){
                map[next.y][next.x]= 1;
                visited[next.y][next.x] = true;
                q.push(next);
            }
        }
    }
    // 익지 않은 토마토가 있는지 확인
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(map[i][j]==0){
                ans = -1;
            }
        }
    }
    cout << ans;

}