(c++)백준 7576번: 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

[풀이]

bfs알고리즘을 이용하여 풀었다.

riped배열에 해당 좌표의 토마토가 보관 후 며칠이 지났을 때 익었는지 저장했다.

만약 다른 익은 토마토로부터 영향을 받았을 때가 더 빠른 일수라면 그걸로 바꿔줬다.

 

 

#include <iostream>
#include <queue>
#include <cstring>//memset
#include <algorithm>//max
using namespace std;

struct Tomato {
	int x, y;//토마토 좌표
};

int M, N;
int Box[1001][1001];
queue<Tomato>q;
int riped[1001][1001];//각 좌표에 있는 토마토가 익는 최소 일수 저장
const int dx[] = { -1,1,0,0 };//뒤,앞
const int dy[] = { 0,0,-1,1 };//왼쪽,오른쪽
bool AllRiped = true;

void input() {
	memset(riped, -1, sizeof(riped));
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> Box[i][j];
			if (Box[i][j] == 0)
				AllRiped = false;
			if (Box[i][j] == 1) {
				riped[i][j] = 0;
				q.push({ i,j });
			}
		}
	}
}

void bfs() {
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			//상자 범위
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			//아직 익지 않은 토마토가 있으면
			if (Box[nx][ny] != -1 && Box[nx][ny] == 0 && riped[nx][ny] == -1) {
				riped[nx][ny] = riped[x][y] + 1;
				q.push({ nx,ny });
			}
			//이미 다른 경로로 익었지만, 지금 경로에서 더 빠르게 익을 수 있으면
			else if (Box[nx][ny] != -1 && Box[nx][ny] == 0 && riped[nx][ny] > riped[x][y] + 1) {
				riped[nx][ny] = riped[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
}

void solution() {
	input();
	//저장될 때부터 모든 토마토가 익어있는 상태이면
	if (AllRiped) {
		cout << 0 << endl;
		return;
	}
	else
		bfs();

	int res = 0;
	//제일 마지막에 익은 토마토의 일수가 최소 일수
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Box[i][j] == 0 && riped[i][j] == -1) {
				cout << -1 << endl;
				return;
			}
			res = max(res, riped[i][j]);
		}
	}
	cout << res << endl;
}

int main() {
	solution();
	return 0;
}