[백준][dfs] 2583 영역 구하기 c++ 구현

목차

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

2583번: 영역 구하기

문제

 

문제 구현 방향

좌표라고 처음에 당황했는데 그냥 좌표값만큼 할당해주면 알아서 색칠된 도형을 표시할 수 있다.

또한 y좌표 기준이 아래부터 시작해서 당황했는데 회전해도 똑같기 때문에 그냥 넣어주면 된다.

물론 나는 Y좌표를 거꾸로 해서 올바르게 넣었다 ㅜ

 

 

 

코드 구현

#include <iostream>
#include<stack>
#include<queue>
#include<algorithm>

using namespace std;

int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int board[100][100] = { 0 };
int visit[100][100] = { 0 };
int N, M, K;
vector<int> v;   //순서대로 넓이 넣어줄 곳
int dfs(int x, int y, int* cnt) {
	visit[y][x] = 1;
	(*cnt)++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (ny <0 || ny>M-1 || nx <0 || nx >N-1)
			continue;
		if (visit[ny][nx] || board[ny][nx])
			continue;
		dfs(nx, ny, cnt);
	}
	return *cnt;

}


int main()
{
	int x1, x2, y1, y2, i, j, p, num=0;
	cin >> M >> N >> K;
	for (i = 0; i < K; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		for (j = M - y2; j < M-y1; j++) {
			for (p = x1; p < x2; p++) {
				board[j][p] = 1;
			}
		}
	}
	for (i = 0; i < M; i++) {
		for (j = 0; j < N; j++) {
			if (board[i][j] == 0 && visit[i][j] == 0) {
				int *cnt = &num;
				*cnt = 0;     
				*cnt = dfs(j, i, cnt);  //전역변수안쓰고 포인터 안쓰고 싶으면 함수 안에서 1호출 후 더해주고 반환
				v.push_back(*cnt);
			}
		}

	}

	sort(v.begin(), v.end());
	cout << v.size() << "\n";
	for (int k : v)
		cout << k << " ";



}

 

별거 아니었는데 전처리에서 해맸다..