백준 (C언어)백준2667번 단지번호 붙히기

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


void apart(int **map,int **visited, int mapsize,int*result,int* count,int i,int j)
{			
	//printf("now:%d %d\n", i, j);
	//if (i + 1 < mapsize && j + 1 < mapsize && 0 < i - 1 && 0 < j - 1)
	//{
	if (i + 1 < mapsize)
	{
		if (visited[i + 1][j] == 0 && map[i + 1][j] == 1)
		{
			visited[i + 1][j] = 1;
			result[count[0]]++;
			apart(map, visited, mapsize, result, count, i + 1, j);
		}
	}
	if (0 <= i - 1)
	{
		if (visited[i - 1][j] == 0 && map[i - 1][j] == 1)
		{
			visited[i - 1][j] = 1;
			result[count[0]]++;
			apart(map, visited, mapsize, result, count, i - 1, j);
		}
	}
	if (j + 1 < mapsize)
	{
		if (visited[i][j + 1] == 0 && map[i][j + 1] == 1)
		{
			visited[i][j + 1] = 1;
			result[count[0]]++;
			apart(map, visited, mapsize, result, count, i, j + 1);
		}
	}
	if (0 <= j - 1)
	{
		if (visited[i][j - 1] == 0 && map[i][j - 1] == 1)
		{
			visited[i][j - 1] = 1;
			result[count[0]]++;
			apart(map, visited, mapsize, result, count, i, j - 1);
		}
	}
	//}
}

void ctoi(char* text, int *arr,int mapsize)
{
	for (int i = 0; i < mapsize; i++)
	{
		arr[i] = text[i]-48;
	}
}

void uparr(int* result, int num)
{
	int tmp;
	for (int i = 0; i < num; i++)
	{
		for (int j = 1; i + j < num; j++)
		{
			if (result[i] > result[i + j])
			{
				tmp=result[i];
				result[i] = result[i + j];
				result[i + j] = tmp;
			}
		}
	}

}

int main()
{
	int** map;
	int** visited;
	int mapsize;
	scanf("%d", &mapsize);
	
	char input[26];
	map = malloc(sizeof(int*) * mapsize);
	visited = malloc(sizeof(int*) * mapsize);
	int result[650] = { 0 };
	for (int i = 0; i < mapsize; i++)
	{
		scanf("%s", input);
		visited[i] = malloc(sizeof(int) * mapsize);
		map[i] = malloc(sizeof(int) * mapsize);
		ctoi(input, map[i],mapsize);
		for (int j = 0; j < mapsize; j++)
		{
			//printf("%d   ", map[i][j]);
			visited[i][j] = 0;
		}
	}
	int count[1] = { 0 };

	for (int i = 0; i < mapsize; i++)
	{
		for (int j = 0; j < mapsize; j++)
		{
			if (visited[i][j] == 0 && map[i][j] == 1)
			{
				apart(map, visited, mapsize, result, count, i, j);
				//printf("out\n");
				if (result[count[0]] == 0)
					result[count[0]]++;
				count[0]++;
			}
		}
	}
	printf("%d\n", count[0]);
	uparr(result,count[0]);
	for (int i = 0; i < count[0]; i++)
	{
		printf("%d\n", result[i]);
	}
	for (int i = 0; i < mapsize; i++)
	{
		free(map[i]);
		free(visited[i]);
	}
	free(map);
	free(visited);
}

 

BFS문제였는데 일단 상당히 더럽게 풀었다. 전역변수를 사용할 수 없는 42서울 특성상 최대한 함수 인자를 맞춰서 넣어봤다. 하지만 딱히 좋은 방법인 것 같지는 않지만 스스로 푼게 뿌듯한 문제!!

​

이 글은 코딩 꼬꼬마 시절에 푼 문제를 보관한 글로 네이버에 저장해둔 글을 옮긴 글입니다.
혹시나 참고하시는 부분에 이상한 부분이나 질문이 생긴다면 남겨주시면 친절히 답변 드리겠습니다.