백준/7576/BFS/토마토

유기태·2022년 5월 24일
0

백준/7576/BFS/토마토
BFS 유형에서 탐색 시작점이 여러개일 경우입니다.
로직은 미로찾기와 마찬가지로 day라는 배열을 따로 선언하여 시작점을 기준으로 너비 우선 탐색을 하여 더 이상 탐색할 곳이 없으면 종료하는것을 전제로 하였습니다.

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 0)
				count++;
			else if (board[i][j] == 1) {
				day[i][j] = 0;
				visited[i][j] = true;
				Q.push({ i,j });
			}
		}
...

위에 코드에 count는 보관함에 존재하는 모든 토마토의 수를 담는 변수입니다.

	while (!Q.empty()) {
		pair<int, int> cur = Q.front(); Q.pop();
		result = day[cur.first][cur.second];
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || board[nx][ny] != 0)continue;
			day[nx][ny] = day[cur.first][cur.second] + 1;
			visited[nx][ny] = true;
			Q.push({ nx,ny });
			recount++;
		}
	}
	if (recount != count)
		result = -1;
	if (count == 0)
		result = 0;
	cout << result << endl;
...

시작점을 queue를 뽑아내고 그 queue에서 파생된 위치들을 다시 queue에 집어 넣는 식으로 반복하면
각 시작점을 기준으로 bfs탐색을 할 수 있습니다. 이 때 익게한 토마토에 위치에 익은 날짜를 새겨줍니다.
새로운 큐를 시작하기전에 result값에 현재 위치에 토마토가 익을 날짜를 넣어주면 마지막에 익은 토마토의 날짜가 들어오고 마지막에 익은 토마토는 상하좌우로 모두 익은 토마토 또는 보관함에 끝이기때문에 while 반복문이 종료합니다.

	if (recount != count)
		result = -1;
	if (count == 0)
		result = 0;
    ...

결과값을 이용해 보관함에 토마토들이 이미 모두 익었을 경우(if(count==0)), 모두 익게하지 못했을 경우(recount!=count), 모두 익게했을 경우를 나눠줍니다.

풀이

첫번째 풀이

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

int board[1000][1000];
bool visited[1000][1000];
int day[1000][1000];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, n;
	int count = 0;
	int recount = 0;
	int result = 0;
	cin >> m >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];

	queue<pair<int, int>> Q;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 0)
				count++;
			else if (board[i][j] == 1) {
				day[i][j] = 0;
				visited[i][j] = true;
				Q.push({ i,j });
			}
		}
	

	while (!Q.empty()) {
		pair<int, int> cur = Q.front(); Q.pop();
		result = day[cur.first][cur.second];
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || board[nx][ny] != 0)continue;
			day[nx][ny] = day[cur.first][cur.second] + 1;
			visited[nx][ny] = true;
			Q.push({ nx,ny });
			recount++;
		}
	}

	if (recount != count)
		result = -1;

	if (count == 0)
		result = 0;

	cout << result << endl;

}
profile
게임프로그래머 지망!

0개의 댓글