[백준/c++] 7576 - 토마토

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

7576번: 토마토

---

1) 풀이

BFS 문제 푸는 주간... 몽롱한 상태로 풀고 몽롱한 상태로 글을 쓰자니 약간 횡설수설할 수 있음에 주의하자!

이전에도 BFS 문제를 풀었으니 이 알고리즘에 대한 전반적인 풀이방법은 이전 글을 참고하자

2021.05.31 - [알고리즘 | 자료구조/백준] - [백준/c++] 1926 - 그림

 

이전 글과 다른 점이 있다면, 1) 탐색을 시작하는 지점이 여러 개이며 2) 단순히 방문 여부가 아니라 토마토가 익는 일수 까지 알아내야 한다.

일단 1)의 경우에는 단순하게 생각해서 탐색을 시작하는 지점, 즉 입력할 때부터 이미 익은 토마토인 경우에는 전부 queue에 넣고 시작하면 된다. 그러면 이미 익은 토마토들이 각각 흩어져있어도 자연스럽게 그 토마토들을 중심으로 탐색을 할 수 있게 된다.

 

2) 의 경우에는 우선  이전글에서 방문여부를 확인하던 bool 배열을 int 배열로 바꿔야 한다.

문제에서 익은 토마토들의 인접한 상하좌우의 토마토들은 하루가 지나면 익는다고 하였으므로, 

앞의 int 배열에 기준점의 값에 각각 1을 더한 값을 상하좌우에 넣어주면 된다.

만약 (x,y)의 값이 0이라면, (x+1,y) (x-1,y) (x,y+1) (x,y-1) 의 값은 1이 된다.

이는 기준점으로부터 떨어져있는 거리와 같은 값을 갖는다! (나중에 거리를 구하는 문제를 풀때도 응용 가능하다는 의미)

 

 또한, 출력 조건을 잘 살펴보면 모든 토마토가 익어있는 경우 0을, 토마토가 모두 익지 못한다면 -1 을, 그 외의 경우에는 토마토가 모두 익는 최소일수를 출력하면 되는데 이때 모든 토마토가 익어있는 경우와 모든 토마토가 익지 못하는 경우를 나눠서 예외처리를 해줘야 한다. 

 

모든 토마토가 익어있는 경우는, queue 의 사이즈를 생각해보면 된다. 

queue의 사이즈가 n*m일 경우에는 모든 토마토가 시작점으로 들어가있다는 의미, 즉 모든 토마토가 이미 익어있는 경우를 의미하므로 0을 출력하고 종료한다.

 

토마토가 모두 익지 못하는 경우는 토마토가 익는 일수를 저장하는 배열을 하나하나 살펴보면 된다.

토마토를 입력하지 전, 일수를 저장하는 int 배열을 모두 0으로 초기화한 뒤, 토마토가 입력될 때 익지 않은 토마토의 칸만 -1로 선언해준다면, 이미 익은 토마토 / 토마토가 없는 칸은 자연스럽게 0으로 아직 익지 않은 토마토는 -1로 초기화가 된다.

그리고 모든 일수를 계산한 뒤 아직까지 -1인 칸이 남아있다면, 익지 않은 토마토가 남아있다는 의미이므로 -1을 출력한다.

 

그외의 경우에는 모든 토마토가 익기 위해 필요한 일수를 max 함수를 통해 구하고 출력한다.

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int dist[1002][1002]; //익는 날짜 계산하는 배열
int board[1002][1002]; // 토마토 입력 배열
int cx[4] = {0,1,0,-1}; //상하좌우 x 좌표
int cy[4]={1,0,-1,0}; // 상하좌우 y 좌표
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;

	cin >> m >> n;
	memset(dist, 0, sizeof(dist)); //익는 날짜 모두 0으로 초기화. 
	queue <pair<int, int>>q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) q.push({ i,j }); //익은 토마토는 큐에 바로 넣음
			else if (board[i][j] == 0) dist[i][j] = -1; //익지 않은 토마토는 -1로 초기화.
			//즉, 이미 익은 토마토 or 토마토가 들어있지 않은 칸만 dist가 0으로 초기화돼있음
		}
	}

	if (q.size() == (n * m)) { //큐의 사이즈가 n_m과 같으면 모든 토마토 좌표가 들어간 것.
		//즉, 모든 토마토가 이미 익어있는 것
		cout << 0;
		return 0;
	}
	while (!q.empty()) {
		pair<int, int>cur = q.front();
		q.pop();
		for (int k = 0; k < 4; k++) {
			int dx = cur.first + cx[k];
			int dy = cur.second + cy[k];
			if (dx <0 || dx >= n|| dy < 0 || dy >= m) continue; //격자모양의 범위를 벗어난다면
			else if (board[dx][dy] == 1|| dist[dx][dy] >= 0) continue; //익은 토마토이면
			q.push({ dx,dy });
			dist[dx][dy] = dist[cur.first][cur.second] + 1;
		}

	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] == -1) { //익지 않은 토마토가 한개라도 있는 경우
				cout << -1;
				return 0;
			}
			else if (dist[i][j] == 0) continue; 
			ans = max(ans, dist[i][j]); 
		}
	}
	
	cout << ans;
}

3) 참고자료