[BAEKJOON] 7576번 : 토 마 토

문 제

 

소 스  코 드

#include <iostream>
#include <queue>
#include <algorithm>


struct Field {
	int x;
	int y;
	int level;
};

bool Search(int **, const int&, const int&);

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

	int M, N;
	std::cin >> M >> N;

	std::queue<Field> spread;
	
	int **tomato{ new int *[N] };
	for (int i = 0; i < N; ++i) tomato[i] = new int[M];

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			std::cin >> tomato[i][j];

			if (1 == tomato[i][j]) spread.push({ i, j, 0});
		}
	}

	int day{ -1 };
	while (!spread.empty()) {
		Field temp = spread.front();
		spread.pop();

		day = std::max(day, temp.level);
		if ((temp.x > 0) && (0 == tomato[temp.x - 1][temp.y])) {
			tomato[temp.x - 1][temp.y] = 1;
			spread.push({ temp.x - 1, temp.y, temp.level + 1 });
		}

		if ((temp.x < N - 1) && (0 == tomato[temp.x + 1][temp.y])) {
			tomato[temp.x + 1][temp.y] = 1;
			spread.push({ temp.x + 1, temp.y, temp.level + 1 });
		}

		if ((temp.y > 0) && (0 == tomato[temp.x][temp.y - 1])) {
			tomato[temp.x][temp.y - 1] = 1;
			spread.push({ temp.x, temp.y - 1, temp.level + 1 });
		}

		if ((temp.y < M - 1) && (0 == tomato[temp.x][temp.y + 1])) {
			tomato[temp.x][temp.y + 1] = 1;
			spread.push({ temp.x, temp.y + 1, temp.level + 1 });
		}
	}


	if (!Search(tomato, N, M)) std::cout << "-1 \n";
	else std::cout << day << '\n';

	for (int i = 0; i < N; ++i) delete[] tomato[i];
	delete[] tomato;

	return 0;
}

bool Search(int ** to, const int& n, const int& m) {
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (0 == to[i][j]) return false;
		}
	}
	return true;
}

 

풀 이

 

• BFS ( 너비 기반 탐색 ) 을 이용한 문제이다.

 위의 그림과 같이, 하루가 지나 갈수록 주변에 있는 전체의 안익은 토마토와 관련이 있기 때문에, 퍼져 나가는 형식의 BFS를 사용하는 것이 맞다.

하지만, 1개가 있을 경우에는 한쪽에서만 퍼져나가지만, 만약 익은 토마토가 1개 이상 일 경우에도 생각을 해야 한다.

 

위의 그림과 같이 2개의 익은 토마토가 있을 경우, 하루에 익은 토마토 2개를 기점으로 안 익은 토마토에게 영향을 끼쳐야 하기 때문에, 이점을 고려하여 구현을 해야한다. 

이 방법은 매우 간단하다. queue에 두 익은 토마토를 넣고, 그 토마토에 대하여 가장 깊은 레벨 까지 내려가는 것을 찾는다면, 전체를 익은 토마토로 만드는데 걸리는 날이 나오게 된다.

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/7576

7576번: 토마토