[C++] 백준 7576번: 토마토

7576번: 토마토

문제 바로가기

이 문제도 2178번: 미로탐색처럼 BFS(너비 우선 탐색)을 활용하는 문제다.

미로탐색의 코드를 활용해서 이 문제를 해결하고자 했는데, 시간초과가 발생했다.

처음에는 현재 박스와 하루가 지나 변화된 박스를 구별하여 두개의 배열을 이용했다.

변화된 박스 배열을 현재 박스 배열에 덮어쓰는 방식으로 했더니 연산량이 과했나보다.

그래서 처음부터 다시 생각했다.

박스를 두 개 생성하는게 아니라, 큐를 두 개 생성했다.

하나는 오늘 익을 토마토들(today), 나머지 하나는 내일 익을 토마토들의 좌표들(tomorrow)이다.

처음에는 각 칸의 상태를 입력받으며 tomorrow에 1인 칸을 담는다.

int M, N;
scanf("%d %d", &M, &N);
int* tomatos = new int[M * N];
queue<pair<int, int>> tomorrow;
queue<pair<int, int>> today;
for (size_t i = 0; i < M * N; i++) {
	scanf("%d", tomatos + i);
	if (tomatos[i] == 1)
		tomorrow.push(make_pair(i % M, i / M));
}

그리고 tomorrow가 비워질 때까지 전체 반복을 계속하는데, 그 내부는 또 today가 비워질 때까지 반복을 계속한다.

처음에는 tomorrow의 각 좌표를 today로 옮기는데, 이 때 이미 방문한(done[i] == true) 좌표는 제외한다.

다음에는 today가 비워질 때까지 인접한(상하좌우) 칸에서 방문하지 않은 칸의 좌표를 tomorrow에 추가하고 현재 칸의 mark에 표시한 후 현재칸을 today에서 제외시킨다.

while (tomorrow.size()) {
	while (tomorrow.size()) {
		if (done[tomorrow.front().second * M + tomorrow.front().first])
			tomorrow.pop();
		else
			today.push(tomorrow.front()), tomorrow.pop();
	}

	while (today.size()) {
		int x = today.front().first;
		int y = today.front().second;

		for (const auto& adjoin : adjoins) {
			int chg_x = x + adjoin.first;
			int chg_y = y + adjoin.second;
			if (chg_x >= 0 && chg_x <= M - 1 && chg_y >= 0 && chg_y <= N - 1)
				if (tomatos[(chg_y) * M + chg_x] == 0 && done[(chg_y) * M + chg_x] == false) {
					tomatos[(chg_y)*M + chg_x] = 1;
					tomorrow.push(make_pair(chg_x, chg_y));
				}
		}
		done[y * M + x] = true;
		today.pop();
	}
OUT:
	day++;
}

위를 마친 후 마지막으로 0인 칸이 있는지 찾고, 적절한 출력을 한 뒤 프로그램을 마친다.

	for (size_t i = 0; i < M * N; i++)
		if (tomatos[i] == 0) {
			printf("-1\n");
			goto END;
		}
	printf("%d\n", day);

END:
	delete[] tomatos;
	delete[] done;
	return 0;

이렇게 코드를 작성하고 VS에 worst case(N: 1000, M: 1000)을 입력했더니 6~7초나 소요되었다.

이유를 도통 못 찾겠어서 질문 검색을 통해 아래로 코드를 간결화 헀고 다시 worst case를 넣었더니 이번엔 3~4초가 소요된다. 혹시 몰라 백준에 제출하니 통과가 되었다.

그래서 기존 코드를 제출했더니 오히려 더 빠른 시간으로 통과가 됐다.

백준의 채점 시스템이 얼마나 고사양인지 알 수 있는 대목이었다.

 

아래는 처음의 기존 코드다.

#include <cstdio>
#include <queue>

using namespace std;

int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	int* tomatos = new int[M * N];

	queue<pair<int, int>> tomorrow;
	queue<pair<int, int>> today;
	for (size_t i = 0; i < M * N; i++) {
		scanf("%d", tomatos + i);
		if (tomatos[i] == 1)
			tomorrow.push(make_pair(i % M, i / M));
	}

	int day = -1;
	bool* done = new bool[M * N];
	for (size_t i = 0; i < M * N; i++)
		done[i] = false;
	pair<int, int> adjoins[4] = { make_pair(0, 1), make_pair(0, -1), make_pair(-1, 0), make_pair(1, 0) };
	while (tomorrow.size()) {
		while (tomorrow.size()) {
			if (done[tomorrow.front().second * M + tomorrow.front().first])
				tomorrow.pop();
			else
				today.push(tomorrow.front()), tomorrow.pop();
		}

		while (today.size()) {
			int x = today.front().first;
			int y = today.front().second;

			for (const auto& adjoin : adjoins) {
				int chg_x = x + adjoin.first;
				int chg_y = y + adjoin.second;
				if (chg_x >= 0 && chg_x <= M - 1 && chg_y >= 0 && chg_y <= N - 1)
					if (tomatos[(chg_y) * M + chg_x] == 0 && done[(chg_y) * M + chg_x] == false) {
						tomatos[(chg_y)*M + chg_x] = 1;
						tomorrow.push(make_pair(chg_x, chg_y));
					}
			}
			done[y * M + x] = true;
			today.pop();
		}
	OUT:
		day++;
	}

	for (size_t i = 0; i < M * N; i++)
		if (tomatos[i] == 0) {
			printf("-1\n");
			goto END;
		}
	printf("%d\n", day);

END:
	delete[] tomatos;
	delete[] done;
	return 0;
}

 

아래는 질문 검색을 통해 고친 코드다.

이 방식은 미로탐색에서 처럼 누적 합을 이용한다.

새로이 익은 토마토는 영향 받은 칸의 값에 1을 계속 더해나간다.

반복을 탈출한 후 그 중 최대값이 걸릴 일수가 되는것이다.

#include <cstdio>
#include <queue>

using namespace std;

int main() {
	int M, N;
	scanf("%d %d", &M, &N);
	int* tomatos = new int[M * N];

	queue<pair<int, int>> today;
	for (size_t i = 0; i < M * N; i++) {
		scanf("%d", tomatos + i);
		if (tomatos[i] == 1)
			today.push(make_pair(i % M, i / M));
	}

	bool* mark = new bool[M * N];
	for (size_t i = 0; i < M * N; i++)
		mark[i] = false;
	int dx[4] = { 0, 0, -1, 1 };
	int dy[4] = { 1, -1, 0, 0 };
	while (today.size()) {
		int x = today.front().first;
		int y = today.front().second;
		while (mark[y * M + x]) {
			today.pop();
			if (today.empty())
				goto OUT;
			x = today.front().first;
			y = today.front().second;
		}

		for (int i = 0; i < 4; i++) {
			int chg_x = x + dx[i];
			int chg_y = y + dy[i];
			if (chg_x >= 0 && chg_x <= M - 1 && chg_y >= 0 && chg_y <= N - 1)
				if (tomatos[(chg_y)*M + chg_x] == 0 && mark[(chg_y)*M + chg_x] == false) {
					tomatos[chg_y * M + chg_x] = tomatos[y * M + x] + 1;
					today.push(make_pair(chg_x, chg_y));
				}
		}
		mark[y * M + x] = true;
		today.pop();
	}

OUT:
	int max = 0;
	for (size_t i = 0; i < M * N; i++) {
		if (tomatos[i] == 0) {
			printf("-1\n");
			goto END;
		}
		if (tomatos[i] > max)
			max = tomatos[i];
	}

	printf("%d\n", max - 1);
END:
	delete[] tomatos;
	delete[] mark;
	return 0;
}