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

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

---

토마토박스를 배열로 준다.

1인 토마토는 익어있어서, 인접한 익지 않은(0인) 토마토를 익게 한다.

토마토맛토

---

부분 코드 설명

#define MAX 1000
typedef struct {
	int x;
	int y;
} Point;
queue<Point> q;
int box[MAX][MAX];
int day[MAX][MAX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };

토마토상자의 최대 길이는 1000이므로 쓰기 편하게 define 해준다.

각 토마토의 위치는 박스 내에서 x, y로 표현할 수 있기에 편하게 Point라는 구조체를 만들어준다.

BFS에 사용할 queue를 선언하고, 입력받은 토마토박스의 상태를 저장할 box 이차원배열, 각각의 토마토가 어느 날짜에 익는지 기록할 day 이차원 배열을 만들어준다.

토마토가 익는 방향은 상하좌우 4방향이므로, dx와 dy를 선언해 각각의 방향을 나타내준다.

 

void bfs(int n, int m) {
	while (!q.empty()) {
		Point cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (box[nx][ny] == 0) {
					box[nx][ny] = 1; //<1>
					day[nx][ny] = day[cur.x][cur.y] + 1; //<2>
					q.push({ nx, ny });
				}
			}
		}
	}
}

BFS 함수이다.

큐에서 토마토를 하나 뽑아 와 Point형 변수 cur에 저장한다.

현재 토마토에서 이동할 수 있는 방향은 상하좌우 4방향이기 때문에, for문을 4번 돌린다.

nx, ny를 선언해 현재 토마토와 인접한 다음 토마토를 하나 고른다.

고른 토마토가 정상적인 범위 내에 있는지, 익었는지 익지 않았는지 검사한다.

<1> : 다음 토마토는 현재 토마토에 의해 익게 되었으므로, box의 해당 토마토 위치에 익었다고 표시한다.

<2> : 다음 토마토가 몇일 걸려서 익었는지 알아야 하므로, day라는 배열의 해당 토마토 위치에다가

현재 토마토가 익은 날짜 + 1 한 값을 넣어준다. (인접한 토마토가 익게 되기까지 하루가 걸리기 때문에)

이 과정들을 거쳤다면 queue에 push 해준다.

 

int main() {
	int n, m;
	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] == 1) {
				q.push({ i, j });
			}
		}
	}
	bfs(n, m);
	int max_day = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (box[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			max_day = max(max_day, day[i][j]);
		}
	}
	cout << max_day << endl;
	return 0;
}

main함수이다.

n과 m을 입력받고, 토마토박스를 입력받는다. 토마토의 상태가 1인 경우는 익어있는 상태로, queue에 넣어주어야 한다.

앞서 입력된 queue를 바탕으로 BFS를 수행한다.

BFS의 수행 후, 토마토가 모두 익은 날짜를 출력해야 하기 때문에 day 배열의 원소 중 최댓값을 찾아준다.

이때 box의 원소 중 0인 원소가 있다면, BFS를 수행했음에도 불구하고 도달하지 못했다는 뜻이다.

이 말은 즉슨 모든 토마토가 익지 못 했다는 것이므로, -1을 출력한다.

앞서 찾은 최댓값을 출력해 주면 된다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 1000
typedef struct {
	int x;
	int y;
} Point;
queue<Point> q;
int box[MAX][MAX];
int day[MAX][MAX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };
void bfs(int n, int m);
int main() {
	int n, m;
	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] == 1) {
				q.push({ i, j });
			}
		}
	}
	bfs(n, m);
	int max_day = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (box[i][j] == 0) {
				cout << -1 << endl;
				return 0;
			}
			max_day = max(max_day, day[i][j]);
		}
	}
	cout << max_day << endl;
	return 0;
}
void bfs(int n, int m) {
	while (!q.empty()) {
		Point cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (box[nx][ny] == 0) {
					box[nx][ny] = 1;
					day[nx][ny] = day[cur.x][cur.y] + 1;
					q.push({ nx, ny });
				}
			}
		}	
	}
}

---

토맛토마토

---