[EPPER] 14회 8번

문제

 

---

풀이

 

이 문제를 보기 전에

 

[EPPER] 10회 7번

[EPPER] 10회 7번

[EPPER] 12회 10번

[EPPER] 12회 10번

이 두개를 보면 편할 것이다.

 

10회 7번에서 지뢰찾기 함수를 편하게 쓰기 위해 테두리를 둘렀었다. 이번에도 테두리를 둘러줄 것이다. 이유는 그때와 같다. 테두리에는 당연히 토마토가 없으니 -1을 저장해야 한다. 그리고 나서 일수를 계산하기 전 우선 토마토를 전부 익게 하는 것이 가능한지 확인한다. 익지 않은 각 토마토에 대해 상하좌우 모두 토마토가 없다면 토마토를 전부 익게 하는 것은 불가능하다. 이를 통해 토마토가 다 익을 수 있음을 확인했다면, 이제 이 과정이 며칠이나 걸릴지 확인한다.

 

토마토가 언제 다 익을지 모르니 while loop를 사용한다. isAll 함수를 이용해 모든 토마토가 익었는지 확인한다. 이 함수가 true를 반환하면 while loop를 빠져나올 수 있다. 익은 토마토를 발견했다면 해당 토마토의 상하좌우 토마토를 체크해둔다. 그리고 모든 토마토를 확인했다면 체크했던 토마토를 한번에 익게 한다. 왜 바로바로 익히지 않고 나중에 익히는지 궁금하다면 12회 10번 문제에서 완료된 공정을 한번에 처리해주는 이유를 살펴보면 될 것 같다. 아무튼 토마토가 전부 익을 때까지 daycnt를 늘리며 반복문을 돌면 된다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

int tomato[1002][1002];
bool checked[1002][1002];

bool isAll(int M, int N) { //전부 익었는지 확인하는 함수
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			if (tomato[i][j] == 0)
				return false;
		}
	}
	return true;
}

int cntDate(int M, int N) {
	int daycnt = 0;
	while (1) {
		if (isAll(M, N)) //전부 익었는지 확인
			break;
		for (int i = 1; i < M + 1; i++) {
			for (int j = 1; j < N + 1; j++) { //익은 토마토인데 상하좌우가 안익은 토마토이면 체크해둠
				if (tomato[i][j] == 1 && tomato[i - 1][j] == 0)
					checked[i - 1][j] = true;
				else if (tomato[i][j] == 1 && tomato[i + 1][j] == 0)
					checked[i + 1][j] = true;
				else if (tomato[i][j] == 1 && tomato[i][j - 1] == 0)
					checked[i][j - 1] = true;
				else if (tomato[i][j] == 1 && tomato[i][j + 1] == 0)
					checked[i][j + 1] = true;
			}
		}
		for (int i = 1; i < M + 1; i++) { //체크했던 토마토 한번에 익게 함
			for (int j = 1; j < N + 1; j++)
				if (checked[i][j])
					tomato[i][j] = 1;
		}
		daycnt++; //하루가 지남
	}
	return daycnt;
}

int main() {
	int N, M;

	scanf("%d %d", &N, &M);
	for (int i = 0; i < M + 2; i++) { //익을 수 있는지 확인하기 쉽게 하려고 상하좌우 한줄씩 추가함
		for (int j = 0; j < N + 2; j++)
			tomato[i][j] = -1;
	}
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			scanf("%d", &tomato[i][j]);
		}
	}
	bool isPossible = true;
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) { //익게 하는게 불가능한지 확인
			if (tomato[i][j] == 0 && tomato[i - 1][j] == -1 && tomato[i + 1][j] == -1 && tomato[i][j - 1] == -1 && tomato[i][j + 1] == -1) {
				isPossible = false;
				break;
			}
		}
	}
	if (isPossible)
		printf("%d", cntDate(M, N));
	else
		printf("-1");
}