백준 7576 토마토 (C++)

안유태·2022년 7월 16일
0

알고리즘

목록 보기
10/239

7576번: 토마토

간단한 BFS 문제였다. 큐에 좌표와 일수를 넣어 제일 마지막으로 나오는 일수가 총 걸린 일수가 된다. 다만 출력 조건을 자세히 봐야한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다. 처음 값을 입력할 때 0이 존재하면 0을 출력하고 BFS 후에 0이 존재하면 -1을 출력하고 둘 다 아니면 일수를 출력한다.
이번 문제는 빠르게 풀었기에 따로 문제점은 없었다.



#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int M, N, res = 0;
int A[1001][1001];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<pair<pair<int, int>, int>> q;

void solution() {
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int day = q.front().second;

		q.pop();
		res = day;

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (A[ny][nx] == -1 || A[ny][nx] == 1) continue;

			A[ny][nx] = 1;
			q.push({ {ny,nx}, day + 1 });
		}
	}

	bool tf = false;
	for (int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if (A[i][j] == 0) tf = true;
		}
	}

	if (tf) cout << -1;
	else cout << res;
}

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

	cin >> M >> N;

	bool tf = false;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> A[i][j];
			if (A[i][j] == 0) tf = true;
			else if (A[i][j] == 1) q.push({ { i,j },0 });
		}
	}

	if (tf) solution();
	else cout << 0;
	
	return 0;
}
profile
공부하는 개발자

0개의 댓글