[백준 7569번] 토마토 - C언어(C++)

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

7569번: 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

 

 

 

---

 solved.ac 레벨 3을 풀면서 인상깊었던 문제라 적어두고 싶어서 기록했다.

 해당 문제는 너비 우선 탐색(BFS)문제이다. 익은 토마토들의 위치를 큐에 넣고 이동할 수 있는 만큼 이동하면 하루가 지난 것으로 계산하였고, unripen 변수에는 아직 익지 않은 토마토들의 개수를 세어 나중에 "아직 익지 않은 토마토들이 남아있지만 접근할 수 없는 경우"에 -1을 출력해야하는 데 이용하였다. 그렇지만 이상하게도 시간초과가 계속 나서 힘들었다. 다음은 그 시간초과가 났던 잘못된 코드이다.

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;

int m, n, h;
int map[100][100][100];
int moved[100][100][100];
queue<tuple<int, int, int>> q;
int unripen = 0;

void input() {
	cin >> m >> n >> h;
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> map[k][i][j];
				if (map[k][i][j] == 0)
					unripen++;
			}
		}
	}
}

void bfs() {
	int dy[4] = { -1,1,0,0 };
	int dx[4] = { 0,0,-1,1 };

	while (!q.empty()) {
		int z = get<0>(q.front());
		int y = get<1>(q.front());
		int x = get<2>(q.front());
		moved[z][y][x] = 1;
		q.pop();

		for (int i = 0; i < 4; i++) { // 상하좌우
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
			if (!moved[z][ny][nx] && map[z][ny][nx] == 0) {
				map[z][ny][nx] = 1;
				unripen--;
			}
		}
		if (z + 1 < h && !moved[z + 1][y][x] && map[z + 1][y][x] == 0) { // 위
			map[z + 1][y][x] = 1;
			unripen--;
		}
		if (z - 1 >= 0 && !moved[z - 1][y][x] && map[z - 1][y][x] == 0) { // 아래
			map[z - 1][y][x] = 1;
			unripen--;
		}
	}
}

void sol() {
	int day = 0;
	while (unripen != 0) {
		for (int k = 0; k < h; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (map[k][i][j] == 1 && !moved[k][i][j]) {
						q.push({ k,i,j });
					}
				}
			}
		}
		if (q.empty() && unripen != 0) {
			cout << -1; // 모든 토마토들이 익지 않음. 그러나 더 이상 이동 불가
			return;
		}
		
		bfs();
		day += 1;
	}
	cout << day;
}

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

	input();
	sol();
	return 0;
}

 내 생각에는 sol() 함수 내의 3중 반복문이 있는데, 이것이 하루가 지날 때마다 계속해서 반복해야하니 64퍼에서 시간초과가 나는게 아닐까 싶다. 

 

 과거에는 다른 방법으로 맞았던 기록이 있었다. map에 있는 익은 토마토의 1의 값을 Level처럼 취급하여 익은 토마토의 Level을 map에 적는 방법이었다. 그리고 그 때도 비슷하게 Ripen, needRipe 변수를 이용해서 모든 토마토들이 익으면 마지막 이동 값을 출력했었다. 오랜만에 생각난 방법이었다. 해당 코드는 맞았었던 코드이다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
	int x;
	int y;
	int z;
}Queue;
Queue q[1000000];
int box[100][100][100] = { 0 }; //세로*가로*높이
int result[100][100][100] = { 0 };
bool visited[100][100][100] = { false };
int M, N, H, cnt = 0, f = 0, r = 0;
int needRipe, Ripen = 0;

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

void BFS() {
	while (f < r) {
		int popx = q[f].x;
		int popy = q[f].y;
		int popz = q[f].z;
		f++;

		//상하좌우
		for (int i = 0; i < 4; i++) {
			int nx = popx + dx[i];
			int ny = popy + dy[i];

			if (0 <= nx && nx <= N - 1 && 0 <= ny && ny <= M - 1) {
				if (!visited[nx][ny][popz]) {
					visited[nx][ny][popz] = true;
					result[nx][ny][popz] = result[popx][popy][popz] + 1;

					q[r].x = nx;
					q[r].y = ny;
					q[r].z = popz;
					r++;

					Ripen += 1;
					if (Ripen == needRipe) {
						printf("%d\n", result[nx][ny][popz]);
						exit(0);
					}
				}
			}
		}
		//위아래
		for (int i = 0; i < 2; i++) {
			int nz = popz + dz[i];

			if (0<=nz && nz<=H-1) {
				if (!visited[popx][popy][nz]) {
					visited[popx][popy][nz] = true;
					result[popx][popy][nz] = result[popx][popy][popz] + 1;

					q[r].x = popx;
					q[r].y = popy;
					q[r].z = nz;
					r++;

					Ripen += 1;
					if (Ripen == needRipe) {
						printf("%d\n", result[popx][popy][nz]);
						exit(0);
					}
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d", &M, &N, &H);
	for (int z = 0; z < H; z++) {
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < M; y++) {
				scanf("%d", &box[x][y][z]);
				if (box[x][y][z] == 0) cnt++;
				else if (box[x][y][z] == 1) {
					q[r].x = x;
					q[r].y = y;
					q[r].z = z;
					r++;
					visited[x][y][z] = true;
				}
				else if (box[x][y][z] == -1)
					visited[x][y][z] = true;
			}
		}
	}

	if (cnt == 0) {
		printf("0\n");
		return 0;
	}

	needRipe = cnt;
	BFS();
	printf("-1\n");
	return 0;
}

 

 요즘은 내가 앞과 같은 방법을 잘 사용하지 않아서.. 하루씩 토마토가 영향을 준 날짜를 세면서도, 큐 안에 하루 동안 영향을 받은  토마토들의 위치를 나중에 다시 세지 않을 수 있는 방법이 없을까 고심했다ㅠ 그렇게 새로운 방법으로 다시 풀었다.

 

 

1. map을 입력할 때 unripen변수에 익지 않은 토마토의 개수를 세고, 익은 토마토는 queue에 넣는다.

2. 바로 bfs를 진행한다. 여기서, 현재 담겨 있는 토마토의 개수만큼 토마토의 탐색을 진행하고 그것을 하루가 지난 것으로 확인한다. 그렇게 queue가 비어질 때까지 bfs를 계속한다.

3. bfs 진행이 완료했음에도 익지 않은 토마토가 남아 있다면 -1을 출력하고, 그렇지 않다면 day-1 값을 출력한다.

=> day-1 값의 이유는 마지막으로 모든 토마토가 익었음에도 아직 탐색 시도를 안 했던 토마토들이 탐색을 진행했기 때문이다.

 

<< 전체 코드 >>

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;

int m, n, h;
int map[100][100][100];
queue<tuple<int, int, int>> q;
int unripen = 0;

void input() {
	cin >> m >> n >> h;
	for (int z = 0; z < h; z++) {
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				cin >> map[z][y][x];
				if (map[z][y][x] == 1) q.push({ z,y,x });
				else if (map[z][y][x] == 0) unripen++;
			}
		}
	}
}

void bfs() {
	int dz[6] = { 0,0,0,0,-1,1 };
	int dy[6] = { -1,1,0,0,0,0 };
	int dx[6] = { 0,0,-1,1,0,0 };
	
	int day = 0;
	while (!q.empty()) {
		int move = q.size();
		while (move--) {
			int z = get<0>(q.front());
			int y = get<1>(q.front());
			int x = get<2>(q.front());
			q.pop();

			for (int i = 0; i < 6; i++) { // 상하좌우
				int nz = z + dz[i];
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || nx < 0 || nz < 0 || ny >= n || nx >= m || nz >= h) continue;
				if (map[nz][ny][nx] == 0) {
					q.push({ nz,ny,nx });
					map[nz][ny][nx] = 1;
					unripen--;
				}
			}
		}
		day++;
	}
	if (unripen == 0)
		cout << day - 1;
	else
		cout << -1;
}

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

	input();
	bfs();
	return 0;
}