[성실코딩 15일차] 백준 #2583 영역 구하기 / DFS

문제는 쉬운데 보통 배열 인덱스 매기는 방향과 다르게

모눈종이의 왼쪽 아래를 (0,0) 오른쪽 위를 (N,M)로 가정해서 입력을 준다.

그리고 칸으로 수를 증가시키는 게 아니라 꼭지점으로 수를 증가시키고 있음

이런 디테일한 부분 놓치지않고 꼼꼼하게 문제푸는 능력 기르기!

#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int map[101][101] = {};
int m, n; // map의 행, 열

// result
int num_area = 0;
int temp_area_size = 0;
vector<int> area_size;

// map 이동
int dx[4] = {0,0,-1,1}; // 열, 상하좌우
int dy[4] = {-1,1,0,0}; // 행

void dfs(int _x,int _y) { // (열,행)
	temp_area_size++; // 넓이 증가
	map[_y][_x] = 1; // 방문표시
	for (int k = 0; k < 4; k++) {  // 상하좌우
		int x = _x + dx[k];
		int y = _y + dy[k];
		if ( (x<0 || x>n-1) ||
			(y<0 || y>m-1)) { // boundary check
			continue;
		}
		
		if (map[y][x]==0) {
			dfs(x, y);
		}
	}
}

int main() {

	// 입력
	int k;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++) {
		int temp_x1, temp_x2, temp_y1, temp_y2;
		cin >> temp_x1 >> temp_y1 >> temp_x2 >> temp_y2;
		// (n,m) (x,y) 열, 행

		int x_size = temp_x2 - temp_x1;
		int y_size = temp_y2 - temp_y1;

		for (int y = 0; y < y_size; y++) { // m 행
			for (int x = 0; x < x_size; x++) { // n 열
				// 왼쪽 위의 꼭지점에서부터
				// 오른쪽 아래방향으로 채워감
				map[temp_y1+y][temp_x1+x] = 1;
			}
		}
	}

	// 연산
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j]==0) { // 하얀공간 발견
				dfs(j,i);// x,y (열,행)
				num_area++;
				area_size.push_back(temp_area_size);
				temp_area_size = 0; //초기화
			}
		}
	}

	// 출력
	sort(area_size.begin(),area_size.end());
	cout << num_area << endl;
	for (int i = 0; i < num_area; i++) {
		cout << area_size[i] << " ";
	}
	return 0;
}