글 읽기 - 반례를 찾지 못 하겠습니다

adfsfsf 5년 전 0

재귀함수 내에서 방향을 이동하는 순서를 일정하게 설정해놨습니다. 또한, check함수의 반환 값은 10,000을 넘지 않으므로 int형으로도 문제가 없습니다. M, N, K가 모두 100 이하의 자연수이므로 K가 0인 경우를 계산할 이유도 없고, 직사각형들이 영역 전체를 채우지도 않으므로 46번째 줄에서 now가 항상 NULL이 아니게 되어서 루프를 돌지 않을 일도 없습니다.

#include <stdio.h>
#include <stdlib.h>
int check(int **map, int i, int j);
int **map, M, N, K;
struct Node {
	int num;
	struct Node *next;
};
int main(void)
{
	int i, j, k, x1, y1, x2, y2;
	long long int count = 0, *num;
	struct Node *node, *now = NULL, *tmp;
	scanf("%d %d %d", &M, &N, &K);
	map = (int **)calloc(N, sizeof(int *));
	for (i = 0; i < N; i++)
		map[i] = (int *)calloc(M, sizeof(int));
	for (i = 0; i < K; i++)//영역을 나누기 위한 루프
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);//직사각형 값 입력
		for (j = x1; j < x2; j++)
		{
			for (k = y1; k < y2; k++)
				map[j][k] = 1;//직사각형 내부의 영역에 값을 채움
		}
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			k = check(map, i, j);
			if (k != 0)
			{
				node = (struct Node *)calloc(1, sizeof(struct Node));
				node->num = k;
				if (now == NULL)
					now = node;
				else
				{
					for (tmp = now; tmp->next != NULL; tmp = tmp->next);
					tmp->next = node;
				}
			}
		}
	}
	for (tmp = now; tmp != NULL; tmp = tmp->next)
		count++;
	num = (long long int *)calloc(count, sizeof(long long int));
	tmp = now;
	for (i = 0; i < count; i++)
	{
		num[i] = tmp->num;
		tmp = tmp->next;
	}
	for (i = 0; i < count; i++)
		for (j = 0; j < count - i - 1; j++)
		{
			if (num[j] > num[j + 1])
			{
				k = num[j];
				num[j] = num[j + 1];
				num[j + 1] = k;
			}
		}
	printf("%lld\n", count);
	for (i = 0; i < count; i++)
	{
		printf("%lld", num[i]);
		if (i != count - 1)
			printf(" ");
	}
	printf("\n");
	free(map);
	return 0;
}
int check(int **map, int i, int j)
{
	if (map[i][j] == 0)
	{
		map[i][j] = 2;
		if (i == 0 && j == 0)
			return check(map, i + 1, j) + check(map, i, j + 1) + 1;
		if (i == 0 && j == M - 1)
			return check(map, i, j - 1) + check(map, i + 1, j) + 1;
		if (i == N - 1 && j == 0)
			return check(map, i - 1, j) + check(map, i, j + 1) + 1;
		if (i == N - 1 && j == M - 1)
			return check(map, i - 1, j) + check(map, i, j - 1) + 1;
		if (i == 0)
			return check(map, i, j - 1) + check(map, i + 1, j) + check(map, i, j + 1) + 1;
		if (j == 0)
			return check(map, i - 1, j) + check(map, i + 1, j) + check(map, i, j + 1) + 1;
		if (i == N - 1)
			return check(map, i - 1, j) + check(map, i, j - 1) + check(map, i, j + 1) + 1;
		if (j == M - 1)
			return check(map, i - 1, j) + check(map, i, j - 1) + check(map, i + 1, j) + 1;
		else
			return check(map, i - 1, j) + check(map, i, j - 1) + check(map, i + 1, j) + check(map, i, j + 1) + 1;
	}
	else
		return 0;
}

djm03178 5년 전 1

check 함수가 언뜻 보면 안전한 것 같지만, 실제로는 아주 위험하게 구성되어 있습니다. 과연 N=1이라도 i=0일 때 i + 1 좌표를 방문해야 할까요?

지금의 코드는 설계가 매우 복잡하면서도 안전하지 않습니다. 경우의 수를 인위적으로 나누면 나눌수록 실수할 가능성이 높으므로, 코드를 가능한 간결하면서도 예외를 처리할 수 있는 코드를 작성하는 것이 좋습니다.

check 함수를 다음과 같이 바꾸면 훨씬 짧으면서도 명확하고 안전한 코드를 작성할 수 있습니다.

int di[4] = { 0, 0, 1, -1 };
int dj[4] = { 1, -1, 0, 0 };

int check(int **map, int i, int j)
{
	if (i >= N || j >= M || i < 0 || j < 0 || map[i][j] != 0)
		return 0;

	map[i][j] = 2;
	int ret = 1;
	for (int k = 0; k < 4; k++)
	{
		int ni = i + di[k];
		int nj = j + dj[k];
		ret += check(map, ni, nj);
	}
	return ret;
}

djm03178 5년 전 0

다른 곳들에서도 개선할 수 있는 부분이 여럿 있습니다. 이 문제는 제한이 작아서 지금 상태로도 통과하는 데에 문제가 없지만,

링크드 리스트를 구현할 때 새로운 원소를 뒤에 추가하기 위해서 지금처럼 전체 리스트를 순회해 들어가는 것은 비효율적입니다. 한 가지 방법으로는 리스트의 끝 노드를 기억해두는 포인터를 하나 더 가지는 방법이 있습니다. 이 문제의 경우 리스트의 순서가 중요하지 않기 때문에 리스트의 맨 뒤가 아닌 맨 앞에 새로운 원소를 삽입하는 것 또한 가능합니다. 이렇게 하면 시간복잡도를 기존의 O(N^2)에서 O(N)으로 줄일 수 있습니다.
정렬을 하기 위해 버블 소트를 사용했는데 이 역시 O(N^2)입니다. 머지 소트, 힙 소트 등 O(NlogN)인 정렬을 이용하면 더 효율적으로 정렬을 수행할 수 있습니다 (평범한 퀵 소트는 O(NlogN) 보장이 안 됩니다.) 이를 직접 구현하는 건 귀찮으니, stdlib.h에 있는 qsort를 사용하면 됩니다.

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

문제

문제

출처

ICPC

반례를 찾지 못 하겠습니다

adfsfsf 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말