[백준][7576] 토마토

이 포스트는 백준 사이트의 토마토(7576) 문제 풀이입니다.

문제

해결 과정

이 문제는 BFS(너비우선탐색)을 활용하여 해결할 수 있습니다.

문제의 입력을 받으면서 익지 않은 토마토 개수(pure_tomato_cnt)를 증가시킵니다.
그리고 그 숫자에 따라 BFS 실행 여부를 결정합니다.

BFS로 창고의 각 칸에 접근하여 익지 않은 토마토가 있는 칸(값이 0)의 개수를 확인하여
확인된 개수가 pure_tomato_cnt와 같다면 모든 토마토가 익은 것이고
값이 다르다면 모든 토마토가 익지 않은 것이므로 -1을 출력하면 됩니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int M, N;
vector<vector<int>> board;
vector<vector<bool>> visited;

struct POS3D {
	int row, col;
};
queue<POS3D> q;
int pure_tomato_cnt = 0;

void input();
int diffuse_tomato();


int main() {
	input();

	if (0 == pure_tomato_cnt) {
        printf("0");
    }
	else {
		q.push(POS3D{ -1, -1 });
		printf("%d", diffuse_tomato());
	}

	return 0;
}


void input() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> M >> N;

    board.assign(N, vector<int>(N, 0));
    visited.assign(N, vector<bool>(N, 0));
    
	for (int row = 0; row < N; ++row) {
		for (int col = 0; col < M; ++col) {
			cin >> board[row][col];

			if (1 == board[row][col]) {
				q.push(POS3D{ row, col });
			}
			else if (0 == board[row][col]) {
				++pure_tomato_cnt;
			}
		}
	}
}

int diffuse_tomato() {
	if (q.empty()) {
        return -1;
    }

    int d_col[4]{ -1, 1, 0, 0 };
    int d_row[4]{ 0, 0, 1, -1 };
	int new_comp_tomato = 0;
	int next_time = 0;
	
    while (q.front().row != -1) {
		bool is_next = false;

		while (true) {
			int row = q.front().row;
			int col = q.front().col;
			q.pop();

			if (row == -1) {
				q.push(POS3D{ -1, -1 });
				break;
			}

			for (int dir = 0; dir < 4; ++dir) {
				int new_row = d_row[dir] + row;
				int new_col = d_col[dir] + col;

				if (new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
					continue;
				if (0 == board[new_row][new_col]) {
					board[new_row][new_col] = 1;
					q.push(POS3D{ new_row, new_col });
					is_next = true;
					++new_comp_tomato;
				}
			}
		}
		
		if (is_next)
			++next_time;
	}

	return (new_comp_tomato == pure_tomato_cnt ? next_time : -1);
}

실행 결과