글 읽기 - 7576 번 토마토 질문있습니다.

whalstn0202 8년 전 0

토마토 여러번 시도했는데 시간초과가 나오네요.

혹시 어떤 부분에서 시간이 많이 걸리고, 어떻게 수정하면 좋을지 조언 좀 해주실분 계신가요?

참고로, 저는 1차원 배열(동적배열)을 사용하였습니다.

감사합니다.

#include <stdio.h>
#include <stdlib.h>

int
main()
{
	int i;
	int* tomato_arr;
	int x, y;
	int days = 0;
	int all_tomato_0 = 0;
	int all_tomato_1 = 0;
	int all_tomato_m1 = 0;

	scanf("%d %d", &x, &y);

	tomato_arr = (int*)malloc(sizeof(int) * (x * y));

	for (i = 0; i < x * y; i++) {
		scanf("%d", &tomato_arr[i]);

		if (tomato_arr[i] == 1) {
			all_tomato_1++;
		}
		else if (tomato_arr[i] == 0) {
			all_tomato_0++;
		}
		else {
			all_tomato_m1++;
		}
	}

	// 모두 1이면 답은 0
	//for (i = 0; i < x * y; i++) {
	//	if (tomato_arr[i] == 1) {
	//		all_tomato_1++;
	//	}
	//}

	if (all_tomato_1 == x * y) {
		printf("0\n");
		free(tomato_arr);
		return 0;
	}

	// 모두 0이면 답은 -1
	//for (i = 0; i < x * y; i++) {
	//	if (tomato_arr[i] == 0) {
	//		all_tomato_0++;
	//	}
	//}

	if (all_tomato_0 == x * y) {
		printf("-1\n");
		free(tomato_arr);
		return 0;
	}

	// 모두 -1이면?
	//for (i = 0; i < x * y; i++) {
	//	if (tomato_arr[i] == -1) {
	//		all_tomato_m1++;
	//	}
	//}

	if (all_tomato_m1 == x * y) {
		printf("-1\n");
		free(tomato_arr);
		return 0;
	}

	while (1) {
		int change = 0;
		int yet_0_exist = 0;
		int cycle = 1;

		for (i = 0; i < x * y; i++) {
			if (i > x * cycle - 1) {
				cycle++;
			}

			if (tomato_arr[i] >= 1 && tomato_arr[i] == days + 1) {
				if (i - 1 >= (cycle - 1) * x && tomato_arr[i - 1] == 0) {
					change = 1;
					tomato_arr[i - 1] = tomato_arr[i] + 1;
				}

				if (i + 1 <= x * cycle - 1 && tomato_arr[i + 1] == 0) {
					change = 1;
					tomato_arr[i + 1] = tomato_arr[i] + 1;
				}

				if (i - x >= 0 && tomato_arr[i - x] == 0) {
					change = 1;
					tomato_arr[i - x] = tomato_arr[i] + 1;
				}

				if (i + x < x * y && tomato_arr[i + x] == 0) {
					change = 1;
					tomato_arr[i + x] = tomato_arr[i] + 1;
				}
			}
		}

		// 하루 지남.
		days++;

		// 아직 tomato_arr[]에 0이 있으면 yet_0_exist를 true(1)로 한다.
		for (i = 0; i < x * y; i++) {
			if (tomato_arr[i] == 0) {
				yet_0_exist = 1;
				break;
			}
		}

		// tomato_arr[]가 하루 지난 후에도 변화가 없고 yet_0_exist가 1이면 더 이상 진행될것이 없다는 뜻 => -1 리턴
		if (change == 0 && yet_0_exist == 1) {
			printf("-1\n");
			break;
		}


		if (yet_0_exist == 0) {
			printf("%d\n", days);
			break;
		}
	}

	free(tomato_arr);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

7576 번 토마토 질문있습니다.

whalstn0202 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말