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

문제 링크이다.

 

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

7576번: 토마토

 

첫 번째 토마토 문제이다.

 

토마토가 몇 번째 날에 어떤 토마토들이 익는 것인지 파악하는 게 중요하다.

 

여러 가지 방법이 있겠지만, 우선 직관적으로 입력을 받으면서 처음부터 익어있는 토마토들을 큐에 담았다.

 

당연하게 초기부터 익어있는 토마토들로부터 확산이 시작될 것이기 때문이다.

 

따라서 입력이 1인 지점들을 큐에 미리 넣어둔다.

 

이후에는 bfs를 수행해주면 되는데 일반적인 bfs 템플릿과 차이가 있는 점은 날짜를 카운트해야 한다는 것이다.

 

이를 위해서는 탐색을 시작할 때, 큐에 몇개가 있는지 생각해서 그 수만큼만 탐색을 탐색을 진행해야 한다.

 

 

이해를 쉽게 하기 위해 시작할 때를 생각해보자.

 

가령 2 * 2로 상자의 크기가 들어오고,

 

0 0

1 1

 

위와 같이 입력이 들어왔다고 가정해보자. 그렇다면 첫 번째 날에는 4방향 확산이 두 번만 일어나야 한다. 1이 두 개이기 때문이다. 즉 확산의 중심이 되는 지점인 1이 두 개이기 때문에 첫 번째 날에는 딱 직전의 1의 개수만큼 실행해줘야 한다.

 

따라서 탐색 직전에 cnt라는 변수를 두어서 그때의 큐의 크기를 잡아두고, 최대 이 크기만큼만 탐색을 수행하도록 했다.

 

그리고 당연하게도, 더 이상 탐색을 할 필요가 없을 때는 탐색을 하지 않도록 해줘야 한다.

 

따라서 토마토의 익은 상태의 변화가 있는지 없는지 확인을 해주는 isChanged라는 변수를 활용했다.

 

변화가 없으면 탐색을 그만두도록 했다. 그래야 Day count를 정확하게 할 수 있다.

 

시작부터 모두 익어있는 경우는 Day가 0일 것이므로 특별한 처리를 해주지 않았다.

 

안 익은 토마토가 있는지는 마지막에 0이 있는지 확인하는 loop로 처리를 해주었다.

 

#include<iostream>
#include<queue>
using namespace std;
int col, row, m[1000][1000];
queue<pair<int, int> > q;
bool vis[1000][1000];
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
int Day = 0;
bool isChanged = false;
void bfs() {
	
	while (!q.empty()) {
		int cnt = q.size();
		isChanged = false;
		while (cnt--) {
			pair<int, int> cur = q.front();
			q.pop();
			
			for (int i = 0; i < 4; i++) {
				int nr = cur.first + dr[i];
				int nc = cur.second + dc[i];
				if (nr < 0 || nc < 0 || nr >= row || nc >= col) continue;
				if (m[nr][nc] == -1 || vis[nr][nc] == true || m[nr][nc] == 1) continue;

				m[nr][nc] = 1;
				q.push({ nr, nc });
				vis[nr][nc] = true;
				isChanged = true;
			}
		}
		if (!isChanged) break;
		Day++;
		
	}
	
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> col >> row;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> m[i][j];
			if (m[i][j] == 1) {
				q.push({ i, j });
				vis[i][j] = true;
			}
		}
	}
	bfs();
	
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (m[i][j] == 0) {
				cout << -1 << '\n';
				return 0;
			}
		}
	}
	
	cout << Day <<'\n';
	return 0;
}