[백준] 2583-영역구하기(C++)

문제링크:https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

전형적인 dfs 문제입니다. (bfs로도 풀이는 가능합니다.)

분리된 공간의 넓이를 출력하면 되는 문제입니다.

위와같이 되어있어서 사각형을 판단하는데 어려움을 가지실 수 있습니다.

하지만 저건 그냥 일반점으로 보아도 무방합니다.

사각형 하나를 그냥 점으로 보세요.

 

 

보이시나요?

0~m, 0~n까지입니다. 

해당위치들을 표시해주고 dfs를 통해서 몇번 탐색이 가능한지 확인하고 결과를 도출합니다.

 

 

정답코드입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int m = 0, n = 0, k =0;
int arr[102][102] = { 0 };
int x, y, x2, y2;

int result[101] = { 0 };
int sum = 0, result_index = 0;
int x_dep[4] = { 1,-1,0,0 };
int y_dep[4] = { 0, 0,-1,1 };

void dfs(int yy, int xx) {
	
	arr[yy][xx] = -1;
	sum++;

	for (int i = 0; i < 4; i++)
	{
		int yyy = yy + y_dep[i];
		int xxx = xx + x_dep[i];

		if (yyy >= 0 && yyy < m && xxx >= 0 && xxx < n) {
			if (arr[yyy][xxx] == 0)
				dfs(yyy, xxx);
		}

	}
	
}
int main() {
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++) {
		cin >> x >> y >> x2 >> y2;

		for (int j = y; j < y2; j++) {
			for (int u = x; u < x2; u++) {
				arr[j][u] = 1;
			}
		}
	}


	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				sum = 0;
				dfs(i, j);
				result[result_index++] = sum;
			}
		}
	}

	sort(result, result + result_index);

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << " ";
	cout << endl;
}

 

저는 dfs가 가장 노력하는만큼 실력이 늘어나는 알고리즘이라고 생각합니다. :0

꼭 직접 작성해보세요. 화이팅!