[algorithm] 백준 7576번 토마토

 

문제 설명 & 접근 방식

익은 토마토(1), 익지 않은 토마토(0), 토마토 없음(-1) 총 3가지 상태가 있으며

익은 토마토는 하루가 지나면 상하좌우의 익지 않은 토마토들을 익게만든다

총 몇일이 지나야 상자 안의 토마토가 모두 익는 지 구해야하는 문제다

 

이 문제는 토마토가 상하좌우 방향으로만 익어가고

다 익는 최소일수를 구해야 하므로 BFS를 사용해야 함을 알 수 있다

일수를 구하는 방법은 시작점으로부터의 거리를 계산하는 방식으로 구하면 된다

 

하지만 익은 토마토가 있는 지점이 여러 곳일 수 있어 익은 토마토가 위치한 곳을 모두 큐에 넣고 BFS를 돌리면 된다

 

코드

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int board[1002][1002];
int vis[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main() {
    queue<pair<int,int>> q;
    int min_day = 0;
    int cnt=0;
    cin >> n >> m;
    for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
                {
                    cin >> board[i][j];
                    if(board[i][j] == 1)
                    {
                        q.push({i,j});
                        vis[i][j] = 1;
                    }
                    if(board[i][j]==-1) vis[i][j] = -1;
                }
        }
    for(int i=0; i<m; i++)
        {
            cnt += count(board[i], board[i]+n, 0);
        }
    if(cnt == 0)
    {
        cout << 0;
        return 0;
    }
    cnt=0;
    while(!q.empty())
        {
            pair<int,int> cur = q.front();
            q.pop();
            for(int tmp=0; tmp<4; tmp++)
                {
                    int nx = cur.X + dx[tmp];
                    int ny = cur.Y + dy[tmp];
                    if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
                    if(vis[nx][ny] || board[nx][ny] == -1) continue;
                    q.push({nx,ny});
                    vis[nx][ny] = vis[cur.X][cur.Y]+1;
                    min_day = max(vis[nx][ny], min_day);
                }
        }

    for(int i=0; i<m; i++)
        {
            cnt += count(vis[i], vis[i]+n, 0);
        }

    if(cnt != 0)
    {
        cout << -1;
        return 0;
    }
    cout << min_day-1;
    return 0;
}

 

board를 입력받을 때 입력값이 1이면 큐에 넣고 방문 표시를 남긴다

만약 board에 0의 개수가 0개일 경우 익은 토마토만 있다는 의미이므로 0을 출력하고 종료한다

 

그 후 첫지점은 설정하지 않고 큐가 빌때까지 상하좌우 탐색하면서 최소일수를 구한다

min_day 변수를 설정하여 최소일수를 구하는데

현재 탐색 중인 구간의 vis 값(새로 익은 토마토의 날짜)과 지금까지 나온 날짜중 더 큰 값을 저장한다

max()를 쓴 이유는 큐의 처리 순서에 의존하지 않기 위함이고 각 노드의 날짜를 최댓값으로 갱신하기 위함이다

단순히 토마토가 익는 날짜를 저장하기 위한 변수이고 max()를 썼다는 이유로 최대값과 관련돼서 혼동할 필요없다

 

첫 지점의 방문표시 값(vis 배열 원소값)을 1로 지정했으므로 출력할 때 -1을 계산해서 출력해야한다

모든 탐색이 끝났는데 0이 남아있다면(익지 않은 토마토가 있다면) -1을 출력하고 종료한다

 

오류

처음에 토마토 없음(-1)의 상태를 입력받았을 때를 따로 처리해주지 않아서

vis값이 0으로 되어있었어서 마지막에 0 개수를 셀 때 카운트돼서 -1이 출력되는 오류가 있었다

if(board[i][j]==-1) vis[i][j] = -1;

이 코드를 입력받는 부분에 추가해주면 해결된다