[C] 백준 - 2583번: 영역 구하기

8월 25일(금) - 그래프와 순회 (2583번)

2583번: 영역 구하기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- dfs 활용하는 방식의 풀이를 예상 -> "단지번호붙이기" or "유기농 배추" 문제와 비슷한 방식의 풀이를 예상

  다만 이전까지 풀이에서는, 영역을 1과 0처럼 이분법적으로 나누어놓기만 했었다

 

- 하지만 이번 문제는 dfs가 돌지 않은 영역들 마다 각각의 넓이도 따로 구해야하므로 모두 0으로 처리하면 골치아픔

- 따라서 dfs가 돌아가는 영역은 1로 초기화하고, 나머지 0으로 처리해왔던 영역은 2,3,4 ... 등으로

   count++을 해주면서 영역마다 다르게 처리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int M, N, K;
int result[101];

int area[101][101];
int visited[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2)
	{
		return 1;
	}
	else if (num1 < num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

void dfs(int x, int y, int value) // 기존 dfs 풀이에서는 int y, int x 순서 -> 따라서 함수안
{
	visited[y][x] = 1;
	area[x][y] = value;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_y < 0 || next_x >= M || next_y >= N)
		{
			continue;
		}
		if (area[next_x][next_y] == 0 && visited[next_y][next_x] == 0) // 기존 dfs 풀이와는 다르게 area[ ][ ] == 1이 아니라 0일때로 조건 변경
		{
			dfs(next_x, next_y, value);
		}
	}
}

int main(void)
{
	scanf("%d %d %d", &M, &N, &K);

	for (int i = 0; i < K; i++)
	{
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

		for (int y = y1; y < y2; y++) // 여기서도 이중 for문을 돌릴때 y먼저 해야할지, x먼저 해야할지 고민했음
		{
			for (int x = x1; x < x2; x++)
			{
				area[y][x] = 1;
			}
		}
	}

	int count = 1;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (area[i][j] == 0 && visited[i][j] == 0) // dfs 안에서와 마찬가지로 area[ ][ ] == 1이 아닌 0일때로 조건 변경
			{
				count++;
				dfs(i, j, count);
			}
		}
	}

	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			result[area[i][j]]++; // 문제점 2) c++에서는 vector에 push하면되지만, c에서는 불가능 -> 참고
		}
	}


	// 문제점 3) 버블정렬 해보려다가 망함
    /*
	int tmp;
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < K - i; j++)
		{
			if (result[j] > result[j + 1])
			{
				tmp = result[j];
				result[j] = result[j + 1];
				result[j + 1] = tmp;
			}
		}
	}
	for (int i = 0; i < count-1; i++)
	{
		printf("%d ", result[i]); // 1 7 13 이 나와야하는데 0 7 13 이 출력
	}
    */
	// 버블정렬 테스트 종료

	printf("%d\n", count - 1);

	qsort(result, count + 2, sizeof(int), compare); // 문제점 3) count-2 부터 count+2까지 하나하나 돌려보다가 어거지로 맞춤 -> 다시봐야함
	for (int i = 2; i <= count; i++)
	{
		printf("%d ", result[i]);
	}

	return 0;
}

- 위의 풀이를 제출한 결과, 틀렸습니다 

-> 기존의 dfs 풀이로 다시 수정

 

1. dfs 호출하는 매개변수 i,j에 각각 기존에는 y,x가 호출되었지만, 이번 풀이에서는 i,j에 각각 x,y가 호출됨

-> 즉, y축 뒤집냐 / 안뒤집냐 차이에 대해서 다시 생각해보며 정리

-> dfs함수의 매개변수로 받을때, (int y, int x)순서이던 것을 (int x, int y)로 변경

-> 이외에는 기존의 dfs 풀이방식의 순서를 그대로 활용

2. result[ ] 에다가 값 저장하는 방식

-> 변수 count를 전역변수로 설정하고, dfs 함수의 매개변수에 추가해놓은 변수 value는 삭제

 

3. qsort, bubble sort 고민

-> result[ ]에 저장되는 값의 개수는 새롭게 만든 변수 idx로 하나하나 카운팅해주면 되므로, qsort의 개수는 결국 idx

 

- 결과적으로 기존의 dfs 풀이를 다시 그대로 활용하며, 전역변수로 count++을 dfs 함수 안에서 진행

-> 이에 따라서 dfs함수와 dfs 호출방식이 이전과 동일 및 단순해졌고, result[ ]에 저장하는 과정도 단순해짐

-> 또한 영역을 1과 0으로 단순하게 이분법적으로 나누던 기존방식으로 돌아오며,

    전체영역을 처음에 1로 초기화 / 직사각형으로 덮히는 영역들은 0으로 초기화

-> 다만 변수 zero_count를 새로 만든뒤에, 따로 나누어지는 영역의 개수를 출력해주어야한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int M, N, K;

int area[101][101];
int visited[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int count;
int result[101];

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2)
	{
		return 1;
	}
	else if (num1 < num2)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

void dfs(int x, int y) // 기존 dfs 풀이에서는 int y, int x 순서
{
	visited[x][y] = 1;

	for (int k = 0; k < 4; k++)
	{
		int next_x = x + dx[k];
		int next_y = y + dy[k];

		if (next_x < 0 || next_y < 0 || next_x >= M || next_y >= N)
		{
			continue;
		}
		if (area[next_x][next_y] == 1 && visited[next_x][next_y] == 0)
		{
			dfs(next_x, next_y);
		}
	}

	count++;
}

int main(void)
{
	scanf("%d %d %d", &M, &N, &K);

	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			area[i][j] = 1;
		}
	}

	for (int i = 0; i < K; i++)
	{
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

		for (int y = y1; y < y2; y++)
		{
			for (int x = x1; x < x2; x++)
			{
				area[y][x] = 0;
			}
		}
	}

	int idx = 0;
	int zero_area = 0;
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (area[i][j] == 1 && visited[i][j] == 0)
			{
				count = 0;
				dfs(i, j);
				result[idx++] = count;
				zero_area++;
			}
		}
	}

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

	printf("%d\n", zero_area);
	for (int i = 0; i < idx; i++)
	{
		printf("%d ", result[i]);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ