[백준 7576] 토마토

0. 제목

• 백준 7576 토마토
• BOJ 7576 토마토
• C++ 7576 토마토

---

1. 문제

https://www.acmicpc.net/problem/7576

---

2. 풀이

• 한단계씩 뻗어나가는 것이 효율적이라 판단하여 BFS를 사용하였다.
• make_pair를 사용하여 좌표쌍을 큐에 push하였다.
• 처음에 배열 값들을 입력받음과 동시에 그 값이 1이면 큐에 push 해주었다.
• 큐에는 탐색할 좌표들을 담아놓는다.
• 큐에 있는 좌표가 더이상 주변의 탐색을 모두 끝낸 좌표일때 pop을 해준다.
• 지금까지 풀었던 bfs문제들은 bfs함수내부에서 매개변수로 들어온 좌표들을 큐에 push 해주었다. 그러나 이 문제는 입력과 동시에 push 를 하였다.
• bfs함수내에서 한번의 루프를 돌때마다 한단계씩 뻗어나가고 서로 떨어져있는 1이었다면 뻗어나가는 중에 만나는 부분이 생길 것이다. 또한 배열 arr의 원소의 값은 해당 좌표까지 지나는 블록수를 저장하고 있기 때문에 한단계씩 뻗어나갈 때마다 1씩 증가시켰다.
• 그렇게 -1을 제외한 0과 1이었던 원소값들이 모두 갱신이 된다.
• bfs를 모두 마치고 나면 arr에는 각 좌표까지의 최소 블록수가 저장되어 있고 그곳에서 최댓값을 찾는다. 마지막에 구현상 1이 더 추가되었기 때문에 -1을 해주면 정답이다.

---

3. 코드

#include <iostream>
#include <queue>
using namespace std;
 
int arr[1001][1001];
int M, N;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
 
void bfs(void){
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx <= 0 || nx > N || ny <= 0 || ny > M) continue;
            if(arr[nx][ny] == 0){
                arr[nx][ny] = arr[x][y] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> M >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 1)
                q.push(make_pair(i, j));
        }
    }
    
    bfs();
    
    int max = 0;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            if(arr[i][j] == 0){
                cout << "-1" << '\n';
                return 0;
            }
            
            if(max < arr[i][j])
                max = arr[i][j];
        }
    }
    cout << max - 1 << '\n';
    
    return 0;
}