BOJ_7576_토마토

이 글은 개발을 공부하고 있는 "학생"의 글입니다. 읽으시면서 참고를 하시되, 틀린 부분이 있을 수 있음을 공지합니다. 혹시 오류를 발견하신 분은 답글 남겨주시면 정말 감사드리겠습니다:)

오늘도 BFS문제를 풀어보겠습니다. BFS를 풀다보면 방문배열을 다르게 다뤄야하는 경우가 종종 있는 것 같습니다. 이번에는 그 방문배열을 다르게 하는 유형을 풀어보도록 하겠습니다. 더해서 너비탐색을 시작하는 점이 여러개인 경우 입니다.

문제 출처 : https://www.acmicpc.net/problem/7576

접근방법

• 문제를 보시면, 바로 grid꼴의 그림을 확인할 수 있습니다.
  -> 2차원 배열을 이용하겠구나, BFS를 사용할 가능성이 높음을 확인할 수 있습니다.
• 익은 토마토의 영향을 해당 토마토의 받아 상, 하, 좌, 우에 있는 익지 않은 토마토가 익게 됨을 볼 수 있습니다.
  -> BFS, 너비로 확장함을 확인할 수 있습니다.
• 입력을 보시면 익은 토마토가 여러개임을 확인할 수 있습니다. 입력을 받을 때, 여러 개의 토마토를 받을 수 있도록 Q를 미리 설정해서 풀이를 진행해야할 것 같습니다.
• 출력에서 요구하는 바는 모든 토마토가 익을 때까지의 최소 날짜를 출력하는 것입니다. 또한 저장될 때부터 모든 토마토가 익어있다면 0을 출력해야합니다. 모두 익지 못할 경우 -1을 출력해야합니다.
  -> BFS 마무리 후, vis를 순회하면서 아직 익지 않은 토마토로 지정해놓은 값이 있다면, -1을 출력하도록 합니다.
  -> 시작점이 0일이 됩니다. vis[시작점의 x좌표][시작점의 y좌표] 값이 0이 되게 됩니다.
  -> 이 값을 1로 시작해두고, 마지막에 1값을 빼주는 식으로 하면 입력의 값들을 그대로 활용할 수 있습니다.
  -> -1은 비어있는 공간, 0은 익지 않은 토마토로 말이죠. 그러면 마지막에 vis를 순회하면서 0의 값이 발견될 경우에 -1을 출력하면 되고, 아닐 경우, 최대값 - 1을 출력하면 됩니다.
• 시간복잡도를 고려해보겠습니다. M, N이 모두 2~1000의 값을 가집니다. O(N*M)이면 대략 1,000,000의 값으로 100만이 나오는군요. O(NM)으로 해결해야겠습니다.
  -> BFS가 적절한 것 같습니다.

시간복잡도 : O(N*M)

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

int m, n;
int arr[1002][1002];
int vis[1002][1002];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {
	cin >> m >> n;
	queue<pair<int, int>> Q;	// 토마토의 위치를 담을 큐
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				vis[i][j] = 1;
				Q.push({ i, j });
			}
			else if (arr[i][j] == -1) {
				vis[i][j] = -1;	// 벽은 -1 처리를 해준다.
			}
		}
	}
	
	// BFS로직을 수행해보자. -> 이미 앞서서 아래의 두 로직수행했다.
	// 1. 익은 토마토 시작점 점을 Q에 집어넣기
	// 2. 익은 토마토의 좌표 방문처리
	while (!Q.empty()) {
		auto curr = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = curr.first + dx[i];
			int ny = curr.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (vis[nx][ny] != 0) continue;	// vis[nx][ny]가 0이 아니면, 방문한 점이거나, 벽이다.
			vis[nx][ny] = vis[curr.first][curr.second] + 1;
			Q.push({ nx, ny });
		}
	}
	
	// 안익은 토마토가 있는지 확인한다.
	// 안익은 토마토가 있으면 -1출력한다.(0이 있는 경우)
	// 안익은 토마토가 없으면 최대값 -1을 출력한다.
	int ret = -1;	// 날짜 결과값 담을 변수
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] == 0) {
				cout << -1;
				return 0;
			}
			ret = max(ret, vis[i][j]);
		}
	}
	cout << ret - 1;
	return 0;
}