글 읽기 - 7576 토마토문제 반례를 도저히 찾을 수가 없네요 ㅜㅜ

muselism 6년 전 0

왜그럴까요 ㅜㅜ

알고리즘은 딱히 bfs등의 자료구조를 적용하지는 않았습니다.

while문을 돌며 토마토를 검사하고 1주변에 있는 토마토들은 2

2주변은 3... 이런식으로 n 주변에 있는 토마토들은 n+1의 값을 줘가며

모든 토마토가 익을때 까지 while문을 돌렸습니다.

질문글들 찾아가며 모든 테스트케이스 돌려봤는데 제대로 뜨던데 ㅠㅠ

반례가 뭘까요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define WIDTH	1000
#define HEIGHT	1000
int calc(int, int);

int main() {
	int width, height;
	scanf("%d %d", &width, &height);
	printf("%d\n", calc(width, height));
}

int calc(int width, int height) {
	char arr[HEIGHT][WIDTH];
	int flag[4] = { 0, };
	int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;

	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 1) flag[0] = 1;
			if (arr[i][j] == 0) flag[1] = 1, cnt1++;
		}
	}

	if (!flag[0] && !flag[1]) return 0;
	if (!flag[0]) return -1;
	if (!flag[1]) return 0;

	while (!flag[2]) {
		flag[3] = 0;
		cnt4++;

		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				
				if (arr[i][j] == cnt4) {
					if (i + 1 < height) {
						if (!arr[i + 1][j]) {
							arr[i + 1][j] = cnt4 + 1;
							flag[3] = 1, cnt2++;
						}
					}
					if (i - 1 > -1) {
						if (!arr[i - 1][j]) {
							arr[i - 1][j] = cnt4 + 1;
							flag[3] = 1, cnt2++;
						}
					}
					if (j + 1 < width) {
						if (!arr[i][j + 1]) {
							arr[i][j + 1] = cnt4 + 1;
							flag[3] = 1, cnt2++;
						}
					}
					if (j - 1 > -1) {
						if (!arr[i][j - 1]) {
							arr[i][j - 1] = cnt4 + 1;
							flag[3] = 1, cnt2++;
						}
					}
				}
			}
		}
		cnt3++;

		if (!flag[3]) return -1;
		if (cnt2 == cnt1) return cnt3;
	}
}

djm03178 6년 전 1

char형 배열인 arr에 %d로 저장할 경우, int의 크기인 4바이트만큼씩을 scanf가 쓰려고 하기 때문에 주변의 다른 원소의 값이 같이 변경되어버립니다. int로 해야 합니다.

그리고 이 방법으로는 시간 초과가 날 것입니다. 예를 들어, 1000x1000 짜리 상자에 오른쪽 아래 끝만 1이고 나머지가 0인 경우, 모든 토마토가 익는 데에 2000일이 소요되는데 2000일 동안 100만개의 칸을 모두 탐색해야 하므로 20억 칸을 조사해야 하는데, 1초 안에 감당이 될 수준이 아닙니다. 지그재그로 돌아가게 만들면 더욱 오랜 시간이 소요됩니다.

djm03178 6년 전 1

queue 라는 자료구조에 대해 알아보시기 바랍니다.

muselism 6년 전 0

아 정말 그렇네요 !! 정말정말 감사드립니다

muselism 6년 전 0

자료구조가 정말 중요하군요 ㅜㅜ 배우기만했지 적용이안되네요 감사합니닷

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

문제

문제

출처

ICPC

7576 토마토문제 반례를 도저히 찾을 수가 없네요 ㅜㅜ

muselism 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

muselism 6년 전 0

muselism 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말