C++ / 7576 / 토마토 ( 너비 우선 탐색 )

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

문제 요약

토마토를 보관하는 큰 창고가 있습니다.

창고이 있는 토마토들은 익어있거나 익지 않은 토마토가 있습니다.

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 됩니다.

인접한 토마토는 왼쪽, 오른쪽 앞, 뒤 네 방향에 있는 토마토를 의미합니다.

대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정합니다.

보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 구해야합니다.

 

1은 익은 토마토

0은 익지 않은 토마토

1은 토마토가 들어 있지 않은 칸

문제 풀이

1. 창고의 사이즈를 입력받습니다.

2. 창고에 토마토를 입력받는데, 익은 토마토일 경우 그 위치를 탐색 할 큐에 푸시합니다.

3. bfs함수를 만듭니다. 탐색 범위를 벗어나거나 이미 체크한 칸이나 지나갈 수 없는 칸이면 continue 합니다.

4. 큐의 선입선출 방식을 활용하면 탐색을 동시에 할 수 있습니다.

5. 만들어진 정답 배열에서 0이 있을경우 ( 익지 않은 토마토가 있기 때문에 ) 0을 출력하고,

없다면 가장 큰 값을 -1 해서( 익은 토마토를 1로 입력 받았기 때문에 ) 출력합니다..

주의할 점

이 문제는 bfs로 풀어야하는데, 토마토가 1개가 아닐때가 있기때문에 한곳의 시작점으로만 탐색하게 하면 원하는 값을 구할 수 없습니다.

큐 ( queue )는 선입선출이라는 특성을 가지고 있기 때문에 탐색을 시작하고 싶은 위치 ( 익은 토마토 위치 )를 큐에 푸시 해두고 bfs를 돌리면 각각의 토마토 위치에서 한스텝씩 동시에 탐색을 할 수 있습니다. 

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

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


queue<pair<int, int>> q;
vector<vector<int>>v;
bool visit[1004][1004];


int n, m;

void bfs()
{

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		visit[x][y] = true;
		q.pop();


		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= m || nx < 0 || ny >= n || ny < 0)
			{
				continue;
			}

			// 이미 체크한 칸이나, 지나갈 수 없는 칸이면 continue
			if (v[nx][ny] != 0)
			{
				continue;
			}

			if (!visit[nx][ny])
			{
				visit[nx][ny] = true;
				v[nx][ny] = v[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}

}

int main()
{
	int a = 0, b = 0;
	cin >> n >> m;

	v.resize(m, vector<int>(n));
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> v[i][j];

			// 토마토 위치 큐에 저장
			if (v[i][j] == 1)
			{
				q.push(make_pair(i, j));
			}
		}
	}

	bfs();

	// 가장 오래 걸린 칸을 저장
	int max = 1;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (v[i][j] == 0)
			{
				max = 0;
				break;
			}
			if (max <= v[i][j])
			{
				max = v[i][j];
			}
		}
		if (max == 0)
		{
			break;
		}
	}

	// 0일차는 빼야함
	max -= 1;
	cout << max;
	return 0;
}

반응형

예제 1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

결과 1

예제 2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

결과 2

예제 3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

결과 3

예제 4

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

결과 4

예제 5

2 2
1 -1
-1 1

결과 5