[C++] 백준 알고리즘 7576번 (토마토)

문제

---

이번에 다뤄볼 문제는 7576번 문제 '토마토'입니다.

토마토 문제에서 연습해야하는 key-point는 BFS입니다.

 

BFS는 너비 우선 탐색을 뜻하는데요.

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

BFS를 활용하여 토마토가 익어나가는것을 탐색 할 수 있으며
탐색되어 익게되는 토마토의 값을 1로 map에서 바꿔줍니다.
visited 2차원 배열에 탐색 횟수를 증가시켜가며 저장해 줍니다.
모든 탐색이 끝난 후 map에 아직 익지 않은 토마토(0)가 존재한다면
이는 토마토가 모두 익지 못하는 상황이므로 예외처리를 해줍니다.
이외에 모든 토마토가 익어있는 상황에 대한 예외처리는 입력을 받으며 체크해줍니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int map[1001][1001];
int visited[1001][1001] = { 0 };
 
int q[1000000][2];
int front = 0, rear = 0;
 
 
int dirX[4] = { -1,1,0,0 };
int dirY[4] = { 0,0,1,-1 };
 
int main() {
 
    int m, n;
    int max = 0;
    int flag = 0;
    int check = 0;
 
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
 
            if (map[i][j] == 0) check = 1;
            if (map[i][j] == 1) {
                q[rear][0] = i;
                q[rear++][1] = j;
                visited[i][j] = 1;
            }
        }
    }
     
    if (check == 0) {
        cout << 0 << endl;
        return 0;
    }
    else {
        int x, y, xx, yy;
 
        while (front != rear) {
            x = q[front][0]; y = q[front++][1];
 
 
            for (int k = 0; k < 4; k++) {
                xx = x + dirX[k]; yy = y + dirY[k];
 
                if (xx<0 || yy<0 || xx >= n || yy >= m || map[xx][yy] != 0) continue;
                if (visited[xx][yy] == 0 || visited[xx][yy] > visited[x][y] + 1) {
                    q[rear][0] = xx; q[rear++][1] = yy;
                    map[xx][yy] = 1;
                    visited[xx][yy] = visited[x][y] + 1;
                }
            }
 
        }
 
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j]>max) max = visited[i][j];
                if (map[i][j] == 0) flag = 1;
            }
        }
         
 
        if (flag == 0) cout << max-1 << endl;
        if (flag == 1) cout << -1 << endl;
 
        return 0;
    }
     
}