[백준 2583] 영역 구하기

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

#include <stdio.h>
#include <stdlib.h>
int M, N, K;
int point[100 + 10][4 + 2];
int board[100 + 10][100 + 10];
int area_cnt;			// 영역의 개수
int area[100 + 10];		// 각 영역의 넓이
int tmp;

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };

void input(void)
{
	scanf("%d %d %d", &M, &N, &K);
	for (int i = 0; i < K; i++) {
		scanf("%d %d %d %d", &point[i][0], &point[i][1], &point[i][2], &point[i][3]);
	}
}

void fill_area(void)
{
	int dx = 0, dy = 0, ux = 0, uy = 0;
	for (int i = 0; i < K; i++) {
		dy = point[i][0];	// 좌표 주의 
		dx = point[i][1];	// x, y 바꿔서 입력 받아야 한다. 
		uy = point[i][2];
		ux = point[i][3];
		for (int a = dx; a < ux; a++) {
			for (int b = dy; b < uy; b++) {
				board[a][b] = 1;	// 입력받은 영역 1로 채우기 
			}
		}
	}
}


int get_area(int x, int y)
{
	board[x][y] = 2;
	tmp++;
	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];
        // 유효 범위 검사
		if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1 || board[nx][ny] == 1 || board[nx][ny] == 2) continue;
		else if (board[nx][ny] == 0) {
			get_area(nx, ny);
		}
	}
	return tmp;
}


void search(void)
{
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0) {
				area[area_cnt] = get_area(i, j);
				area_cnt++;
				tmp = 0;	// 다음 영역의 넓이를 구하기 위해 tmp변수 초기화
			}
		}
	}
}


int comp(int *p, int *q)	//qsort 위한 비교함수
{
	if (*p > *q) return 1;
	if (*p < *q) return -1;
	return 0;
}

void output(void)
{
	printf("%d\n", area_cnt);
	
	qsort(area, area_cnt, sizeof(int), comp);
	for (int i = 0; i < area_cnt; i++) {
		printf("%d ", area[i]);
	}
}


int main()
{
	input();
	fill_area();
	search();
	output();
	return 0;
}

 

// fill_area() 함수

다른 DFS 문제랑 크게 다른점은 없지만, 주의해야 할 부분은 처음 좌표를 받아 영역을 1로 표시해줄 때 이다.

문제에서는 "직사각형의 왼쪽 아래 꼭지점의 x, y 좌표값"을 (0, 2)로 입력받지만, 코드상에서는 2행 0열이다. 따라서 우리가 흔히 알고 있는, 좌표평면 위에서의 x, y를 코드로 구현할 때는 y, x로 해야한다는 것이다.