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

이전 미로 문제와 달리 BFS 의 시작지점이 한군데가 아니라 아닐 경우를 생각해보는 문제이다

0,0 을 큐에 처음 넣었던과 달리, 좌표를 돌며 시작 지점이 될 수 있는 모든 곳을 그냥 그대로 큐에 넣으면 된다

이전처럼 visited 대신 좌표의 거리 값 배열 dist를 만들고 dist의 좌표 값 자체로 방문 여부를 파악하게하고 갱신하여

최단거리를 구하면 다익기까지의 최소 시간을 구할 수 있는 문제였다

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

7576번: 토마토

#include<bits/stdc++.h>
using namespace std;

int board[1004][1004];			// 보드 선언
int dist[1004][1004];			// 좌표 상에서의 거리, 익기까지 걸린 날짜
int n, m;						// 입력될 보드 크기
int dx[4] = {-1, 1, 0, 0};		// 이동 방향 나타낼 좌표
int dy[4] = {0, 0, -1, 1};		// 상하좌우
int min_dist = 0;				// 최소로 걸리는 시간(최단거리 구하기 BFS)

int main(){
	ios::sync_with_stdio(0);	// 입출력 속도 향상
	cin.tie(0);					// 그 중 입력 처리속도 향상
	queue<pair<int, int>> Q;	// BFS는 좌표를 큐나 튜플을 사용해서 처리해 나간다
	
	cin >> m >> n;				// 보드 크기 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];		// 보드의 각 좌표에 값 넣기
			if (board[i][j] == 1)	// 익은 것은 보드 좌표가 1, 익었다면 큐에 해당 좌표 넣기
			{
				Q.push({i, j});
			}
			if (board[i][j] == 0)	// 익지 않은 것은 보드 좌표가 0, 익지 않았으면 거리를 -1로 둔다
			{						// -1 이 아니라 다른 음수여도 상관없다. 편의상 양수일 거리와
				dist[i][j] = -1; 	// 익은 것인 0과 구분하기 위해 음수로 둔다
			}
		}
	}
	while (!Q.empty())				// 큐가 비지 않았다면 실행(더 갈 곳이 없지 않다면 실행)
	{
		auto current = Q.front();	// 큐 맨 앞의 값을 current 라 하고 저장
		Q.pop();					// 큐 맨 앞의 값을 큐에서 뺌
		for (int direction = 0; direction < 4; direction++)	 // 진행 가능한 4가지 방향의 경우를 생각함 
		{
			int nx = current.first + dx[direction];			// 예상 이동방향의 새 좌표.first
			int ny = current.second + dy[direction];		// 예상 이동방향의 새 좌표.second
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)		// 새 좌표가 보드 밖을 벗어나는 값이라면
			{
				continue;									// continue
			}
			if (dist[nx][ny] >= 0)							// 새 좌표가 가진 거리 값이 0보다 크다면
			{												// -1이 아니란 말이므로 이동 불가이다
				continue;									// 그러므로 continue
			}
			dist[nx][ny] = dist[current.first][current.second] + 1;	// 이동하면 새 좌표의 거리 값는 이전 좌표의 거리 값 +1
			Q.push({nx, ny});								// 이동한 새 좌표의 값을 큐에 넣어 다음 이동 목표를 탐색하게 한다
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (dist[i][j] == -1)		// 보드의 좌표를 모두 돌며 좌표의 거리 값이 -1 인 아직 이동 못한 곳이 있다면
			{
				cout << -1;				// -1 을 출력하고 거기서 리턴한다 (모두 익히지 못하는 경우)
				return 0;
			}
			min_dist = max(min_dist, dist[i][j]);	// 모든 좌표를 돌며 각 좌표가 가진 거리 값을 비교, 최대 값을 갱신한다
		}											// 최단 거리를 구하는 BFS 알고리즘이므로
	}												// 그 중 최대 값이 최소한 걸리는 시간이 된다
	cout << min_dist;								// 좌표들이 가진 거리 값의 최대값(최소 소요 시간)을 출력한다
	
	return 0;
}