문제

• n*m의 창고에 토마토를 보관한다.
• 보관 후 하루가 지나면 익은 토마토의 인접한 곳에 있는 토마도가 익는다.
• 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구하시오
• 칸에 토마토가 들어있지 않을수도 있다.

입력

0: 익지 않은 토마토
1: 익은 토마토
-1: 없음

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

출력

8

풀이

풀이 1 - 시작점이 여러개

• 저장될 때부터 모든 토마도가 익어있으면 0을 출력해야함
• 토마토가 모두 익지 못하는 상황이면 -1 출력

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
이 예제에서 오른쪽 가장 하단에 있는 토마토를 제외한 모든 토마토가 익지 않았다.
토마토는 인접한 토마토 (상하좌우)를 익힐 수 있다.
(4,6)을 큐에 넣는다

하루가 지나면
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
이렇게 (4,6)-> (4,5), (3,6)이 익는다.
(4,6)을 pop하고 해당 인덱스에서 상하좌우로 갈 수 있는 인덱스를 큐에 넣는다.
다음 노드인 (4,5)랑 (3,6)이 둘다 0이고, 방문한 적이 없기 때문에 (4,5), (3,6)를 큐에 넣고 해당 isVisit을 1로 바꾼다.

이틀이 지나면
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 1 1 1
(4,5) -> (4,4), (3,5)
(3,6) -> (2,1)

토마토가 모두 익을 때까지 걸리는 최소 시간을 구하는 것이기 때문에 상하좌우로 한칸씩 늘어날 때마다 하루가 지난다. 따라서 걸리는 일수는 시작점에서부터 현재 인덱스까지의 거리와 같다.
따라서 dist[1002][1002]로 두고 거리를 일수로 생각하며 풀 수 있다.

순서
1. 토마토 상태를 입력받는다.
- 만약 토마토가 익은 상태이면 나중에 방문하기 위해 queue에 넣는다.
- 만약 토마토가 안익은 상태이면 익은 상태로 바꿔줘야 하기 때문에 거리를 -1로 명시한다.
- dist
0: 방문 안한 것
-1: 안익은 것
1 2 3 4 ...: 시작점으로부터의 거리
2. 큐에 들어있는 노드를 하나씩 접근하여 상하좌우의 토마토 상태를 확인한다.
- 해당 노드의 상하좌우에 익지 않은 토마토가 존재하면 해당 토마토가 익는데까지 걸리는 시간을 -1에서 갱신하고 다음으로 방문할 곳으로 큐에 저장한다.
- 만약 방문한 경우이거나 토마토가 존재하지 않거나 토마토가 이미 익어있는 경우 즉, dist>=0 인 경우에는 pass한다.

3. 큐를 모두 돌고 나면 토마토 박스의 상태를 확인한다.
   • 한칸씩 방문하면서 dist안에 -1 즉, 익지 않은 토마토가 존재하면 -1을 출력한다.
   • 입력받을 때부터 모든 토마토가 익어있었다면 0을 출력해야한다. 익은 토마토의 dist는 0이므로 2에서 pass되어 dist[i][j]가 모두 0이다.
     

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[1002][1002]; //그림
int dist[1002][1002]; //dist : 이전노드 +1 = 걸리는 시간을 뜻함

//아래 오른쪽 위 왼쪽
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);
    
    int n, m;
    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];
            //익은 토마토는 큐에 push -> 방문 예정
            if(board[i][j]==1) Q.push({i, j});
            //익지 않은 토마토는 거리가 -1
            if(board[i][j]==0) dist[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>=m || ny<0) continue;
            
            //방문한 경우이거나 이미 익어있는 토마토의 경우는 pass
            if(dist[nx][ny]>=0) continue;
            
            //다음 노드 dist 갱신
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx, ny}); //다음으로 방문할 곳 저장
        }
    }
    
    int ans=0; //모든 토마토가 익어있으면 0, 모두 익지 못하는 상황이면 -1 출력
    
    //박스 상태 확인하기
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            //익지 않은 토마토가 존재하면
            if(dist[i][j] == -1){
                cout <<-1; return 0;
            }
            ans = max(ans, dist[i][j]);
        }
    }
    
    
    cout <<ans;
    
}