[백준/C++] 7576번. 토마토

문제

7576번: 토마토

---

1. 마지막 풀이

사고 과정

그냥 BFS 돌리면 되지 않을까? 칸도 1,000 x 1,000으로 널널한데.

 

1. 토마토 입력, 익은 토마토는 바로 큐에 넣는다.
   1. 이때 시간도 함께 체크해둔다.
2. 익은 토마토를 꺼내, 4방향 토마토를 익히고 큐에 넣는다.
3. 모든 토마토가 익었는지 검사한다.

 

코드

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

int n, m;
std::vector<std::vector<int>> tomato;

bool promise(int x, int y) {
	if (x < 0 || m <= x || y < 0 || n <= y || tomato[x][y] != 0) {
		return false;
	}

	return true;
}

bool isAllTomatoesRipe() {
	for (auto& vec : tomato) {
		for (auto& i : vec) {
			if (i == 0) {
				return false;
			}
		}
	}

	return true;
}

int main() {
	std::cin >> n >> m;
	
	tomato.resize(m, std::vector<int>(n));
	// x, y, time
	std::queue<std::tuple<int, int, int>> ripe_tomato;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			std::cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				ripe_tomato.emplace(std::make_tuple(i, j, 0));
			}
		}
	}

	int offset[4][2] = {
		{ -1, 0 },
		{ 0, 1 },
		{ 1, 0 },
		{ 0, -1 }
	};

	int day = 0;
	while (ripe_tomato.empty() == false) {
		std::tuple<int, int, int> pos = ripe_tomato.front();
		ripe_tomato.pop();
		day = std::get<2>(pos);

		for (int i = 0; i < 4; i++) {
			int new_x = std::get<0>(pos) + offset[i][0];
			int new_y = std::get<1>(pos) + offset[i][1];

			if (promise(new_x, new_y)) {
				tomato[new_x][new_y] = 1;
				ripe_tomato.emplace(std::make_tuple(new_x, new_y, day + 1));
			}
		}
	}

	if (isAllTomatoesRipe() == false) {
		day = -1;
	}

	std::cout << day;
}

 

결과

 

가볍게 성공. 메모리랑 시간은 좀 많이 썼다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/43918099

온갖 난해함이 난무하는 토마토 문제. 그나마 해석 가능한 건 이 코드 정도.

 

크게 다를 건 없지만, short와 bool을 사용해 메모리를 줄이고, tuple을 사용하지 않아 좀 더 빠르다.

---

강평

알고리즘 스터디에서 추천해 손댄 토마토 문제. 앞으로 먹을 토마토가 많다.