[백준] 7576번 토마토

문제: 7576번: 토마토

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m, n; // m: 가로, n: 세로
    cin >> m >> n; 

    int dx[4] = { 1, 0, -1, 0 };
    int dy[4] = { 0, 1, 0, -1 };

    vector<vector<int>> board(n);
    vector<vector<int>> visit(n);
    vector<vector<int>> dists(n);
    queue<pair<int, int>> nexts;

    int startCnt = 0;
    for (int i = 0; i < n; i++) {
        board[i] = vector<int>(m);
        visit[i] = vector<int>(m);
        dists[i] = vector<int>(m);

        for (int j = 0; j < m; j++) {
            cin >> board[i][j];

            if (board[i][j] == 1) {
                nexts.push(make_pair(i, j));
                visit[i][j] = 1;
                dists[i][j] = 0;

                startCnt++; // 이 값이 m*n 값과 같으면 0 출력, 0이면 -1 출력
            }
        }
    }

    if (startCnt == 0)
        cout << -1;
    else if (startCnt == m * n)
        cout << 0;
    else {
        while (!nexts.empty()) {
            pair<int, int> cur = nexts.front();
            nexts.pop();

            for (int i = 0; i < 4; i++) {
                int nx = cur.first + dx[i];
                int ny = cur.second + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (visit[nx][ny] == 1 || board[nx][ny] == -1) continue;

                board[nx][ny] = 1; // 토마토 익었다 ~_~
                dists[nx][ny] = dists[cur.first][cur.second] + 1;

                nexts.push(make_pair(nx, ny));
                visit[nx][ny] = 1;
            }
        }

        int max = -1;
        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 0)
                    flag = true; // 익지 않은 토마토가 있어..

                if (max < dists[i][j])
                    max = dists[i][j];
            }
        }
        if (flag)
            cout << -1;
        else
            cout << max;
    }

    
    return 0;
}

 

그냥 BFS 를 살짝 응용하면 바로 풀리는 문제다. 출력은 가장 긴 dist 값을 출력해주면 된다. 이 문제는 2178번 미로탐색 문제 풀었으면 바로 쉽게 풀 수 있다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x09강 - BFS

[실전 알고리즘] 0x09강 - BFS