백준 7576_토마토 문제풀이 in C++

2022년 04월 05일 in Devlog on Algorithm Last modified at: 2022년 04월 10일

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 하루에 한 칸씩 익은 토마토들의 영향이 전이되어 익지 않은 토마토들이 익게 된다.
• 이때, 모든 토마토가 익게 되는 최소한의 시간을 구하여라.
• 첫번째 줄에는 토마토 상자 크기가 주어진다. (M, N)
• 이어서 토마토 맵의 값이 주어진다.

  • -1은 토마토가 안 들어있는 칸
  • 0은 익지 않은 토마토가 들어있는 칸
  • 1은 익은 토마토가 들어있는 칸

접근 방법

---

• ‘여러 군데에 익은 토마토가 있을 시 어떻게 접근해야 하는가?’를 해결하면 이 문제를 풀 수 있게 된다. 해당 문제는 칸 입력 시 1일 때, 그 좌표 값을 큐에 넣어 BFS 반복 좌표를 해당 좌표로 선정한다. 또, 미로 탐색(최소 이동)과 비슷하게 풀이하면 되는데 해당 문제는 이동 할 수 있는(덜 익은 토마토가 있는) 모든 칸을 이동하는데 걸리는 시간을 구하면 된다. 즉, 모든 칸을 가면 되기 때문에 Check를 굳이 할 필요가 없다.

풀이 순서

---

1. 토마토 맵 입력 시 1인 경우(익은 토마토인 경우) 해당 좌표를 큐에 넣는다.
2. BFS 함수 작성 시 다음 칸이 이동 가능하면 현재 자리 값에 + 1 한 값을 다음 칸에 대입한다.
3. 이렇게 만들어진 토마토 맵을 다시 반복문을 이용해서 탐색한다. 이때, 0이 하나라도 존재하면 -1을 출력하고 프로그램 종료, 아니라면 result 값과 맵의 각 값을 비교하며 최대로 큰 값을 대입한다.

소스코드

---

#include <iostream>
#include <queue>

using namespace std;

int tomatoMap[1000][1000];
queue<pair<int, int>> q;
int result = 0;
int M, N;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
void tomatoBFS() {
	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

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

			if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
				if (tomatoMap[nx][ny] == 0) {
					tomatoMap[nx][ny] = tomatoMap[xx][yy] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

void tomato() {
	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tomatoMap[i][j];

			if (tomatoMap[i][j] == 1) {
				q.push(make_pair(i, j));
			}
		}
	}
	tomatoBFS();


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tomatoMap[i][j] == 0) {
				cout << -1 << "\n";
				return;
			}

			if (result < tomatoMap[i][j]) {
				result = tomatoMap[i][j];
			}
		}
	}

	cout << result - 1 << "\n";
}
int main() {
	tomato();

	return 0;
} 

문제 풀이 결과

---