[백준 7576] 토마토 (BFS)

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

풀이

길게 늘여놓으면 이해가 안될 것같아 순서대로 풀이를 적겠습니다.

1. 입력받을 map, 좌표, 큐를 선언합니다.

2. 입력받으면서 익은토마토의 좌표를 큐에 넣습니다.

3. bfs함수를 돌립니다.

4. bfs함수에서, 익은 토마토좌표 주위의 안익은 토마토좌표의값을 익은 토마토좌표에 저장된값으로부터 +1해줍니다.

(bfs에서 익은 토마토좌표를이용해 연산하므로 1번에서 언급한 큐를 전역으로 선언한 이유입니다.)

5. 안익은토마토의 좌표를 +1해주는 이유는 0이아니게해주고(익게해주고), 궁극적으로는 답인 최소날짜를 구하기위함입니다. 익은게 1로 표현되므로 날짜를 구하기 좋은 조건입니다. 이 때, ans(날짜)를 0으로 선언하면 예제입력5를 입력하면 -1이 됨으로 1로 선언해둡니다.(예제코드를 입력해보다가 오류가 나서 발견했습니다.)

6. 주위 토마토를 익게하는 연산을 할 때 마다 ans(날짜)를 더 큰값으로 초기화해줍니다.

7. bfs연산을 마치고 map을 확인합니다. 좌표값이 0인 좌표가 존재하면 익을 수 없으므로 -1출력 뒤 종료합니다. 그리고 5번에서 설명했듯이 map의 좌표는 최소 일수들로 갱신된상태입니다. 그런데 연산최초에 익은 토마토주위의 값은 2인데, 2일이 지난게 아니라 1일이 지난것이므로 출력할 때 -1해줍니다.

주의할 것은 ans를 0이 아닌 1로 선언해야한다는 것입니다. 

(예제입력을 발견하다가 수정했더니 정답이네요,, 이부분에서 명확하게 1로선언해야하는 이유나 이렇게 애매한 선언을 방지하기위한 장치나, 다른 방법의연산방법이 있다면 알려주세요!!)

코드

#include<iostream>
#include<queue>
using namespace std;
int map[1000][1000];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int m, n;
queue<pair<int, int>>q;
//ans를 0으로 해두면 예제입력5 설명불가
int ans = 1;
void bfs();
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> m >> n;
	//토마토있는 좌표만 큐에넣음
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1)
			{
				q.push({ i,j });
			}
		}
	}
	bfs();
	//bfs를 돌리고나면 map은 토마토가익는 날(+1)로초기화됨
	//토마토있을때1이므로 그주변이 익을 때 1일이아닌 2일로표현되므로
	//답을 출력할때 -1해줘야함.
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//0이있으면 익지못한곳이있으므로 -1출력
			if (map[i][j] == 0)
			{
				cout << -1 << '\n';
				return 0;
			}
		}
	}
	//30~32행에서 언급했듯이 -1해줘야함. 
	cout << ans - 1 << '\n';
}
void bfs()
{
	while (!q.empty())
	{
		int x = q.front().second;
		int y = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				if (map[ny][nx] == 0)
				{
					//익은곳주위의 토마토가안익은곳을 +1해줌
					//+1해주는 이유는 최소날짜를 구하기위함
					map[ny][nx] = map[y][x] + 1;
					q.push({ ny,nx });
					//초기화시켜줌.
					if (ans < map[ny][nx])
					{
						ans = map[ny][nx];
					}
				}
			}
		}
	}
}

결과