[ DFS/BFS - 7576 ] 토마토(C++/BFS)

---

접근법

 

BFS, DBF의 구조를 이해했다면, 이 문제를 보고 바로 BFS를 떠올렸을 것이다. BFS는 너비 탐색이다. 문제를 보면, 토마토는 익은 토마토에 의해서만 익을 수 있고, 우리는 전체 토마토가 익는 최소 일수를 구해야 한다. 따라서 BFS의 접근법이 더 맞다.

 

또한, 이전엔 노드와 노드사이의 하나의 간선만 존재하였다. 하지만, 익은 토마토를 기준으로 상,하,좌,우를 모두 탐색해야 한다. 그리고 시작 노드는 처음 토마토가 주어졌을 때 모든 익은 토마토에 대하여 시작해야 한다.

 

 

3번재 예제를 살펴보면, (0,0),(4,6)의 토마토가 처음 익은 토마토로 주어졌다. 따라서 시작 노드를 (0,0) 하나로 특정하면, (6,4)에 의해 익어진 토마토의 경우의 수를 고려하지 못하기 때문이다.

 

BFS의 기본 구조는 처음 Queue에 들어가는 것이 시작 노드이다. 그렇다면, 우리는 토마토의 상태를 입력 받을 때, 익은 토마토 즉, 상태가 1인 토마토를 모드 Queue에 넣은 뒤 BFS를 시작하면 될 것이다.

 

하나 더 생각 할 것은 바로 최소 일수이다. 익은 토마토를 기준으로 하루 뒤 상,하,좌,우의 토마토가 익는 상황이다. 따라서, 탐색 과정에서 우리는 익은 토마토를 기준으로 상,하,좌,우의 토마토의 상태가 0인 토마토를 탐색해서 Queue에 넣음으로써 다음 Step에서 방문 할 것이다. 

 

 

(0,0) 토마토가 익은 상태이므로 하루 뒤 (1,0) 토마토의 상태가 1로 변할 것이다. (1,0)의 토마토가 현재 익었으므로 (2,0)의 토마토는 상태가 0이기 때문에 하루 뒤 (2,0) 토마토의 상태가 1로 변할 것이다. 하지만, 이는 처음 기준으로 2일 뒤이다. 그리고 우리는 (6,4)에 의한 익어가는 과정도 고려해야 한다.

 

공통적인 특징이 있다면, 안 익은 토마토는 모두 0이고 토마토가 없는 경우는 -1이다. 그리고 토마토가 익은 상태는 모두 0보다 큰 값을 가진다. 따라서 토마토가 익는 것을 상태를 1로 바꾸는 것이 아닌, 현재 노드의 값 + 1로 하게 된다면, BFS가 진행되면서 한 노드(토마토)에 의하 탐색되는 상,하,좌,우의 토마토의 상태값은 익은 토마토의 값 + 1이 되기 때문에, 익어가는 날짜를 자동적으로 계산할 수 있다. 이때, 시작이 1이였으므로 결과에서 1만 빼주면 된다.

---

정답

#include<iostream>
#include<queue>
#pragma warning(disable:4996)

using namespace std;

const int MAX = 1001;

queue<pair<int32_t,int32_t>> q;
int32_t ars32_Graph[MAX][MAX];
int32_t s32_Width, s32_Height;

void DoBFS();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int32_t s32_I, s32_J, s32_Result = 0;

	cin >> s32_Width >> s32_Height;

	for (s32_I = 0; s32_I < s32_Height; s32_I++)
	{
		for (s32_J = 0; s32_J < s32_Width; s32_J++)
		{
			cin >> ars32_Graph[s32_I][s32_J];	// 익은 토마토를 바로 queue에 넣어서 시작 Node 설정
			if (ars32_Graph[s32_I][s32_J] == 1)
			{
				q.push(make_pair(s32_I,s32_J));
			}
		}
	}

	DoBFS();

	/* 날짜 계산 및 출력  */
	for (s32_I = 0; s32_I < s32_Height; s32_I++) {
		for (s32_J = 0; s32_J < s32_Width; s32_J++) {
			// 익지않은 토마토(0)가 존재할 경우
			if (ars32_Graph[s32_I][s32_J] == 0) {
				cout << "-1\n";
				return 0;
			}

			// 토마토가 익은 날짜 계산
			if (s32_Result < ars32_Graph[s32_I][s32_J]) {
				s32_Result = ars32_Graph[s32_I][s32_J];
			}
		}
	}
	cout << s32_Result - 1 << "\n";

	return 0;
}


void DoBFS()
{

	pair<int32_t, int32_t> st_Node;
	int32_t s32_I, s32_DeltaHeight, s32_DeltaWidth;

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

	// Loop
	while (!q.empty())
	{
		// 하나를 뺀다
		st_Node = q.front();	// Height, Width
		q.pop();

		// Action( 생략 )

		// 다시 집어넣음
		for (s32_I = 0; s32_I <4; s32_I++)
		{
			// 인접 노드 및 방문 확인

			s32_DeltaHeight = st_Node.first + dy[s32_I];
			s32_DeltaWidth = st_Node.second + dx[s32_I];

			if (0 <= s32_DeltaHeight && s32_DeltaHeight < s32_Height && 0 <= s32_DeltaWidth && s32_DeltaWidth < s32_Width)
			{
				if (ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] == 0)
				{
					ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] = ars32_Graph[st_Node.first][st_Node.second] + 1;
					q.push(make_pair(s32_DeltaHeight, s32_DeltaWidth));
				}
			}
		}
	}

}

 

기존 BFS 틀은 유지되지만 탐색하는 방향, 노드 값의 차이가 있을 뿐이다.

 

	for (s32_I = 0; s32_I < s32_Height; s32_I++)
	{
		for (s32_J = 0; s32_J < s32_Width; s32_J++)
		{
			cin >> ars32_Graph[s32_I][s32_J];	// 익은 토마토를 바로 queue에 넣어서 시작 Node 설정
			if (ars32_Graph[s32_I][s32_J] == 1)
			{
				q.push(make_pair(s32_I,s32_J));
			}
		}
	}

 

입력받은 토마토의 상태가 1이면 바로 Queue에 넣는다. 

 

void DoBFS()
{

	pair<int32_t, int32_t> st_Node;
	int32_t s32_I, s32_DeltaHeight, s32_DeltaWidth;

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

	// Loop
	while (!q.empty())
	{
		// 하나를 뺀다
		st_Node = q.front();	// Height, Width
		q.pop();

		// Action( 생략 )

		// 다시 집어넣음
		for (s32_I = 0; s32_I <4; s32_I++)
		{
			// 인접 노드 및 방문 확인

			s32_DeltaHeight = st_Node.first + dy[s32_I];
			s32_DeltaWidth = st_Node.second + dx[s32_I];

			if (0 <= s32_DeltaHeight && s32_DeltaHeight < s32_Height && 0 <= s32_DeltaWidth && s32_DeltaWidth < s32_Width)
			{
				if (ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] == 0)
				{
					ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] = ars32_Graph[st_Node.first][st_Node.second] + 1;
					q.push(make_pair(s32_DeltaHeight, s32_DeltaWidth));
				}
			}
		}
	}

}

 

BFS를 잘 보면, dx, dy 배열이 있다. 이는 익은 토마토(st_Node)를 기준으로 상,하,좌,우로 움직이기 위함이다. Queue에 들어있는 노드는 현재 익은 노드로 인접한 안 익은 토마토들을 익게 할 토마토이다. 

 

// 다시 집어넣음
for (s32_I = 0; s32_I <4; s32_I++)
{
	// 인접 노드 및 방문 확인

	s32_DeltaHeight = st_Node.first + dy[s32_I];
	s32_DeltaWidth = st_Node.second + dx[s32_I];

	if (0 <= s32_DeltaHeight && s32_DeltaHeight < s32_Height && 0 <= s32_DeltaWidth && s32_DeltaWidth < s32_Width)
	{
		if (ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] == 0)
		{
			ars32_Graph[s32_DeltaHeight][s32_DeltaWidth] = ars32_Graph[st_Node.first][st_Node.second] + 1;
			q.push(make_pair(s32_DeltaHeight, s32_DeltaWidth));
		}
	}
}

 

s32_DeltaHeight, s32_DeltaWidth는 상,하,좌,우의 토마토이다. 주어진 토마토의 범위 내 인지 확인한 뒤, 해당 위치의 토마토가 0이면, 현재 노드값 + 1을 해당 토마토의 상태값으로 하기 때문에, 몇일 째 익는지 확인할 수 있다. 그리고 다음 Step에서는 해당 토마토가 익은 토마토이기 때문에 Queue에 집어 넣는다.