(백준 2583번 영역 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 5

반차쓰고 곱창국수 먹고 카페에서 한시간 졸고 푼 문제.. 역시 낮잠을 자니 머리가 잘 돌아가는군!

 

백준 2583번

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

2583번: 영역 구하기

// 백준 2583번

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

constexpr int MAX_N = 101;

class Graph {
public:
	int M, N; 
	int arr[MAX_N][MAX_N];
	int dir_x[4] = { 0, 1, 0, -1 };
	int dir_y[4] = { 1, 0, -1, 0 };
	int comp = 0;
	vector<int> v;
	Graph(int M, int N) : M(M), N(N) {
		//★ arr[MAX_N][MAX_N] = {1}이라고 하면 (0,0)만 1로 초기화된다!!
		for (int i = 0; i < M; i++) {
			fill_n(arr[i], N, 1);
		}
	}

	void addBlock(int lx, int ly, int rx, int ry) {
		for (int j = ly; j < ry; j++) {
			for (int i = lx; i < rx; i++) {
				arr[j][i] = 0;
			}
		}
	}
	void printBlock() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				cout << arr[i][j] << ' ';
			}
			cout << '\n';
		}
	}
	bool isInside(int x, int y) {
		if (x < 0 || x >= M || y < 0 || y >= N) return false;
		return true;
	}

	void bfs_comp() {
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(arr[i][j]) {
					v.push_back(bfs(i, j));
					comp++;
				}
			}
		}
		printf("%d\n", comp);
		sort(v.begin(), v.end());
		for (auto nodes : v) {
			printf("%d ", nodes);
		}
	}
private:
	int bfs(int x, int y) {
		int nodes = 1; 
		arr[x][y] = 0; 
		for (int i = 0; i < 4; i++) {
			int nx = x + dir_x[i];
			int ny = y + dir_y[i];
			if (isInside(nx, ny) && arr[nx][ny]) {
				nodes += bfs(nx, ny);
				arr[nx][ny] = 0;
			}
		}
		return nodes;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M, K;
	cin >> M >> N >> K;
	Graph g(M, N);
	for (int i = 0; i < K; i++) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		g.addBlock(x1, y1, x2, y2);
	}
	g.bfs_comp();
	return 0;
}

 

⭐0이 아닌 숫자로 2차원 int 배열 초기화하기 

2차원 배열을 1로 초기화하기 위해서는 fill_n함수를 사용하자!