글 읽기 - 접근을 잘못한 걸까요?

kimdr123 8년 전 0

초등부 기출문제라서 다른사이트에서 돌려보면 87점이라는 부분점수를 얻었는데

테스트케이스 크기가 커고 숫자들이 짤려 skip으로 나와있어서 어디를 잘못했는지 알수가 없네요.

접근방식은 이렇습니다.

일단 배열에 input값을 다 넣어주고 함수를 통하여 다음작업을 수행합니다.

사이클을 한번 똘때마다 u라는 카운트변수를 하나씩 올려가면서 배열의 크기와 비교를 해서 u보다 숫자들은 모두 -1로 변화를 시킵니다.

다 바꾼 배열을 DFS를 통하여 섬의 개수가 몇개인지 카운터를 해주고요. (처음 -1을 만나면 카운터 올리고 그녀석과 이웃한녀석들은 0으로 바꾸어줍니다.

이차포문을 활용하기때문에 중복계산을 피하기 위해서)

카운터를 한 것을(소스에선 count) result란 배열에 사이클돌때마다 넣어줍니다. 이렇게 하면 while문이 끝났을때 u변수에 증가에 대한 섬의 개수(count)가

출력될것이기에..

그리고 마지막으로 제가 섬을 센다고 배열변수들을 -1, 0으로 바꾸어놨기 때문에 기존에 함수를 통해서 (copy)만들어놨던 복사본을 다시 가져와서

수를 이상하게 보는일이 없도록 해주었습니다.

여기서 하나 질문이 있는데 input이 최대 100개라고 하여 제가 while문을 100번만 돌면될거 같아서 100이라는 조건을 걸어주었는데

배열크기가 꼭 100이라는게 아니고 더 작을수도 있잖아요? 이걸 어떻게 효율적으로 바꿀수 있을까요?

그리고 어디가 틀렸는지좀 알려주세요!

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

int arr[101][101];
int arr_copy[101][101];
int result[101];
int i, j;
int copy(int n);
int change_minus(int n,int m);
int check(int n,int m,int input);
int compare(const void*a, const void *b)
{
	return (*(int*)b - *(int*)a );
}

int main()
{
	int input;
	int count = 1;
	int u = 1;
	int a, b;
	int flag = 1;

	scanf("%d", &input);

	for (i = 0; i < input; i++)
		for (j = 0; j < input; j++)
			scanf("%d", &arr[i][j]);


	copy(input);

	
	while (flag)
	{

	
	change_minus(input, u);

	for (i = 0; i < input; i++)
	{
		for (j = 0; j < input; j++)
		{
			if (arr_copy[i][j] == -1)
			{
			
				check(i,j,input);
				count++;
				/* 출력테스트
				for (a = 0; a < input; a++)
				{
					for (b = 0; b < input; b++)
					{
						printf("%3d ", arr_copy[a][b]);
					}printf("\n");
				}
				
				printf("\n\n");
			/	*/
			}
			
			
		}
	}
	
	result[u] = count;
	count = 0;
	copy(input);


	if (u==101)
	{
		
		flag = 0;
	}
	u++;

	}//while문 끝

	
	qsort(result, 101, sizeof(int), compare);

	for (i = 0; i < 101; i++)
	{
		if (result[i] != 0)
		{
			printf("%d", result[i]);
			break;
		}
	}
	

	system("pause");
	return 0;
}

int copy(int n)
{
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			arr_copy[i][j] = arr[i][j];
		}
	}

	return 0;
}


int change_minus(int n,int u)
{
	

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			if (arr_copy[i][j] > u)
				arr_copy[i][j] = -1;
		}
	}

	return 0;
}

int check(int n,int m,int input)
{
	arr_copy[n][m] = 0;

	if (arr_copy[n + 1][m] == -1 && n + 1 < input)
		check(n + 1, m, input);

	if (arr_copy[n][m+1] == -1 && m + 1 < input)
		check(n, m+1, input);

	if (arr_copy[n-1][m] == -1 && n-1>=0)
		check(n -1 , m, input);

	if (arr_copy[n][m-1] == -1 && m-1>=0)
		check(n, m-1, input);


}

yukariko 8년 전 0

안녕하세요. 같은 전북대학교 학생이신거같은데 실례지만 과를 물어볼 수 있을까요?

kimdr123 8년 전 0

현재 전자과 재학중입니다

yukariko 8년 전 0

그렇군요

저는 컴퓨터공학과인데

acm icpc 대회준비를 위한 스터디 인원을 모으고있어서 여쭤본거였어요 ㅎㅎ

타과생이면 팀을 꾸릴 수 없어서 아쉽네요

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