[C++]백준 7576번: 토마토

문제

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

7576번: 토마토

 

문제이해

• N과 M을 입력한다.
• 각 칸에 대한 정보를 담은 N x M 크기의 상자를 입력한다.
• 모든 토마토가 익을 때까지의 최소 날짜를 출력한다. 다만 모든 토마토가 익지 못하는 상황의 경우 -1을 출력한다.

모든 토마토가 익을 때까지의 최소 날짜를 구하기 위해서는 너비우선탐색(BFS)을 이용하여 문제를 해결해야 한다.

 

큐(queue)에 현재 익은 토마토들의 정보를 넣고 pop 하며 pop 한 토마토의 주변 토마토들을 다시 큐(queue)에 넣어주는 작업을 반복하면 된다. 다만 모든 토마토가 익지 않는 경우를 찾기 위해 상자에 있는 0의 총개수를 저장해 놓고 너비우선탐색(BFS)이 끝났을 때 지워진 0의 개수와 비교하여 전부 다 익었는지 아니면 전부다 익지 못했는지를 확인해야 한다.

 

다음은 너비우선탐색(BFS)을 사용하여 문제를 해결한 코드이다.

 

문제풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int M, N, X;
vector<vector<pair<int, bool>>> tomato;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void bfs() {
	queue<pair<pair<int, int>, int>> q;
	int zeroCount{};
	for (int i{ 0 }; i < N; i++) {
		for (int a{ 0 }; a < M; a++) {
			if (tomato[i][a].first == 1) {
				q.push(make_pair(make_pair(i, a), 0));
				tomato[i][a].second = true;
			}
			else if (tomato[i][a].first == 0)
				zeroCount++;
		}
	}
	int result{ 0 };
	while (!q.empty()) {
		pair<pair<int, int>, int> top = q.front();
		result = top.second;
		q.pop();
		for (int i{ 0 }; i < 4; i++) {
			int newDx = top.first.first + dx[i];
			int newDy = top.first.second + dy[i];

			if (newDx > -1 && newDx < N && newDy > -1 && newDy < M
            && !tomato[newDx][newDy].second && tomato[newDx][newDy].first != -1) {
				zeroCount--;
				q.push(make_pair(make_pair(newDx, newDy), top.second + 1));
				tomato[newDx][newDy].second = true;
			}
		}
	}
	if (zeroCount > 0)
		cout << "-1";
	else
		cout << result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> M >> N;
	for (int i{ 0 }; i < N; i++) {
		vector<pair<int, bool>> flr;
		for (int a{ 0 }; a < M; a++) {
			cin >> X;
			if (X != -1)
				flr.push_back(make_pair(X, false));
			else
				flr.push_back(make_pair(X, true));
		}
		tomato.push_back(flr);
	}
	bfs();
}

우선 상자의 정보는 2차원 벡터를 통해 저장하였고 상자 안의 토마토의 상태와 방문했는지에 대한 여부가 들어가있다.

 

void bfs()

이후 bfs의 queue에서는 x값과 y값 그리고 현재 지난 날짜를 저장하고 있으며 맨 처음 2차원 벡터로 저장된 상자를 순회하면서 익은 토마토의 정보를 queue에 저장하고 익지 않은 토마토의 개수를 확인했다. 이후 익지 않은 토마토를 방문하며 bfs를 실시하였다.

 

bfs가 끝난 후에 익지 않은 토마토가 남아있을 경우 -1을 출력하였고 익지 않은 토마토가 없을 경우 최소 날짜를 출력하였다.

 

문제후기

bfs를 사용하면 어렵지 않게 해결할 수 있는 문제였다.