[C++] 백준 BOJ 7576 토마토

문제 링크 : https://boj.kr/7576

이 문제보다 기본 개념의 문제는 BOJ 2178 미로 탐색을 참고

컨셉을 잡는 데에 상당히 어려울 수 있지만 알고보면 기본적인 BFS 문제인 것 같다.

map을 int형 컨테이너로 하나 만들어 입력 정보를 받고 이 정보를 visited로 사용하면 된다.

현재 탐색하는 위치 정보는 별도의 구조체를 만들어 여기에 x, y 좌표와 BFS 탐색의 몇번째 단계에 해당하는지 level 변수를 추가하였다.

입력 받을 때 익은 토마토를 발견하면 그 즉시 바로 큐에 담는다.

큐에 담긴 순서대로 BFS를 수행하면 문제가 쉽게 풀리게 된다.

BFS를 다 수행한 이후엔 다시 한번 전수조사를 해서 안익은 토마토를 체크했다.

#include <bits/stdc++.h>
 
using namespace std;
const int dir[4][2] = {{0,  -1}, {-1, 0}, {1,  0}, {0,  1}}; // 4방향
 
struct node{
    int x;
    int y;
    int level; // 토마토가 익기 시작하는 일수
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
    int M, N;
    cin >> N >> M;
    vector<vector<int> > map(M + 2, vector<int>(N + 2, -1));
    queue<node> tomato;
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) {
                // 초기에 이미 익어있는 토마토들을 큐에 저장 (시작 노드)
                tomato.push({i, j, 0});
            }
        }
    }
 
    int result = 0;
    while(!tomato.empty()){
        node toma = tomato.front();
        tomato.pop();
        // 현재 노드를 기준으로 상,하,좌,우 안익은 토마토 탐색
        for(int i = 0; i < 4; i++) {
            int nextX = toma.x + dir[i][0];
            int nextY = toma.y + dir[i][1];
            if(map[nextX][nextY] == 0) {
                // 맵에서 익은 토마토로 변경
                map[nextX][nextY] = 1;
                // 다음 노드의 좌표와 level을 저장시킴
                node nextToma = {nextX, nextY, toma.level + 1};
                // 큐에 다음 노드 저장
                tomato.push(nextToma);
                // 최대 레벨 값 저장
                result = max(result, nextToma.level);
            }
        }
    }
 
    // 수행 후에도 안익은 토마토가 있는지 체크
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if(map[i][j] == 0) {
                result = -1;
                break;
            }
        }
    }
    cout << result;
 
    return 0;
}