[백준] 7569. 토마토

백준 문제 풀이

 

[백준] 7569. 토마토

7569번: 토마토

 

---

문제 해석

7576. 토마토 문제에서 z축이 추가된 문제이다.
BFS를 사용해서 풀 수 있다.

토마토가 보관된 상자의 x y z 크기가 주어지고, 입력으로 토마토의 정보가 주어진다.
1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 없는 칸이다.
또한 토마토가 무조건 하나 이상 있는 경우만 입력으로 주어진다고 했다.

이 때 토마토가 모두 익는 데 며칠이 걸리는지를 답으로 출력하면 된다. BFS를 통해 익은 토마토 주변으로 익혀 나가며 계산할 것이고, 곁에 붙어있는 토마토가 없어 익힐 수 없는 토마토가 존재하는 경우를 구하기 위해 안 익은 토마토의 개수를 변수로 저장해 둘 것이다.

 

풀이

사용한 변수들

 

다음과 같이 처음 토마토 정보를 입력 받을 때, 익은 토마토와 안 익은 토마토에 대해서 개수를 세고, 배열에 저장하는 과정을 수행한다.

	// 1. 토마토 정보를 입력 받음
	cin >> size_of_x >> size_of_y >> size_of_z;
	for (int z = 0; z < size_of_z; z++)
	{
		for (int y = 0; y < size_of_y; y++)
		{
			for (int x = 0; x < size_of_x; x++)
			{
				cin >> tomatoes[x][y][z];
				if (tomatoes[x][y][z] == 1) {
					// 익은 토마토일 경우에는 riped_tomatoes에 튜플로 좌표를 저장해둠
					riped_tomatoes.push_back(make_tuple(x, y, z));
				}
				else if (tomatoes[x][y][z] == 0) {
					// 안 익은 토마토는 개수 세어 두기
					num_of_unriped_tomatoes++;
				}
			}
		}
	}

 

그 후에는 BFS를 통해 익은 토마토 주변을 탐색하며 옆에 있는 토마토들을 익혀 간다

	// 2. riped_tomatoes에 있는 토마토들을 하나씩 탐색하며 bfs로 익지 않은 토마토를 익혀감
	for (int i = 0; i < riped_tomatoes.size(); i++)
	{
		explore_with_bfs(get<0>(riped_tomatoes[i]), get<1>(riped_tomatoes[i]), get<2>(riped_tomatoes[i]));
	}

 

이 이후부터는 처음 시도했던 방법이랑 조금 고친 방법으로 나뉜다.

방법 1.  조금 시간이 오래 걸리지만 정답이긴 했던 방법

BFS function은 다음과 같이 작성했다.

void explore_with_bfs(int x, int y, int z) {
	queue<tuple<int, int, int>> q;

	q.push(make_tuple(x, y, z));
	while (!q.empty())
	{
		tuple<int, int, int> current_tomato = q.front();
		int cur_x = get<0>(current_tomato);
		int cur_y = get<1>(current_tomato);
		int cur_z = get<2>(current_tomato);
		q.pop();

		for (int j = 0; j < 6; j++)
		{
			int next_x = cur_x + dx[j];
			int next_y = cur_y + dy[j];
			int next_z = cur_z + dz[j];

			if (next_x >= 0 && next_x < size_of_x && next_y >= 0 && next_y < size_of_y && next_z >= 0 && next_z < size_of_z) {
				if (tomatoes[next_x][next_y][next_z] == 0) {
					// 익지 않은 토마토를 익힐 때
					tomatoes[next_x][next_y][next_z] = tomatoes[cur_x][cur_y][cur_z] + 1;
					q.push(make_tuple(next_x, next_y, next_z));
					num_of_unriped_tomatoes--;
				}
				else if (tomatoes[next_x][next_y][next_z] > tomatoes[cur_x][cur_y][cur_z] + 1) {
					// 이미 익혔던 토마토지만 원래 익히는 날짜보다 더 빨리 익힐 수 있을 때
					tomatoes[next_x][next_y][next_z] = tomatoes[cur_x][cur_y][cur_z] + 1;
					q.push(make_tuple(next_x, next_y, next_z));
				}
			}
		}
	}
}

튜플로 토마토의 좌표를 저장해 두고, 처음에 익어 있던 토마토에 대해서 BFS를 한번씩 수행해 보는데
이때 주변에 있는 토마토 중 0(아직 익은 적이 없는 토마토)인 토마토와 원래 익히는 날짜보다 더 빨리 익을 수 있는 토마토를 익혀 준다.

 

그 후 날짜를 계산해 본다. 한번씩 쭉 탐색하면서 가장 큰 숫자를 찾았다.

	// 3. num_of_unriped_tomatoes(익지 않은 토마토의 개수)를 보고, 0이 아닐 경우에는 익지 못하는 것도 있기 때문에 -1을 출력하고, 아닐 경우에는 다 익히는 데 걸리는 날짜를 적는다
	if (num_of_unriped_tomatoes > 0) {
		cout << "-1";
	}
	else {
		// 전부 탐색하면서 가장 큰 숫자를 찾음, -1한 것이 답
		int max_date = 1;
		for (int z = 0; z < size_of_z; z++)
		{
			for (int y = 0; y < size_of_y; y++)
			{
				for (int x = 0; x < size_of_x; x++)
				{
					if (tomatoes[x][y][z] > max_date) {
						max_date = tomatoes[x][y][z];
					}
				}
			}
		}

		cout << max_date - 1;
	}

 

방법 2. 위와 같이 시간이 오래 걸려서 개선한 방법

변수를 조금 수정했다.

익은 토마토의 좌표를 queue로 수정하고, max_date를 토마토를 익히는 과정에서 구할 수 있도록 전역변수로 설정해 두었다.

 

이전의 방법에서 시간을 개선하기 위한 방법은 queue로 수정하면서, 익은 토마토의 queue에서 하나씩 꺼내면서 다음을 익혀가게 하는 것이었다. 따라서 BFS function에서 "이미 익은 것이지만 익는 날짜가 현재보다 커서" 다시 날짜를 정해 주던 과정이 필요 없어졌다.

그래서 max_date도 나중에 다시 탐색하고 구할 필요 없이, 토마토를 익히는 과정에 구할 수 있게 되었다.

고친 BFS function은 다음과 같다.

void explore_with_bfs() {
	while (!riped_tomatoes.empty())
	{
		tuple<int, int, int> current_tomato = riped_tomatoes.front();
		int cur_x = get<0>(current_tomato);
		int cur_y = get<1>(current_tomato);
		int cur_z = get<2>(current_tomato);
		if (tomatoes[cur_x][cur_y][cur_z] > max_date) {
			max_date = tomatoes[cur_x][cur_y][cur_z];
		}
		riped_tomatoes.pop();

		for (int j = 0; j < 6; j++)
		{
			int next_x = cur_x + dx[j];
			int next_y = cur_y + dy[j];
			int next_z = cur_z + dz[j];

			if (next_x >= 0 && next_x < size_of_x && next_y >= 0 && next_y < size_of_y && next_z >= 0 && next_z < size_of_z) {
				if (tomatoes[next_x][next_y][next_z] == 0) {
					// 익지 않은 토마토를 익힐 때
					tomatoes[next_x][next_y][next_z] = tomatoes[cur_x][cur_y][cur_z] + 1;
					riped_tomatoes.push(make_tuple(next_x, next_y, next_z));
					num_of_unriped_tomatoes--;
				}
			}
		}
	}
}

 

또한 마지막에 답을 구하는 것도 간단해졌다

	// 3. num_of_unriped_tomatoes(익지 않은 토마토의 개수)를 보고, 0이 아닐 경우에는 익지 못하는 것도 있기 때문에 -1을 출력하고, 아닐 경우에는 다 익히는 데 걸리는 날짜를 적는다
	if (num_of_unriped_tomatoes > 0) {
		cout << "-1";
	}
	else {
		cout << max_date - 1;
	}

 

 

결과

수정하기 전

수정 이후

수정하기 전 전체 소스코드 (Github) / 수정한 후 전체 소스코드 (Github)