백준 2583 영역 구하기(C++) (다시 풀어볼것!)

백준 2583 영역 구하기

풀이 코드

#include <bits/stdc++.h>
using namespace std; 
#define y1 rrrr
int M, N, K, x1, y1, x2, y2;
int arr[104][104];
int visited[104][104];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<int> ret;

int DFS(int y, int x){
	visited[y][x] = 1;
	int ret = 1;
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(ny < 0 || nx < 0 || ny >= M || nx >= N || visited[ny][nx] == 1) continue;
		if(arr[ny][nx] == 1) continue;
		ret += DFS(ny, nx);
	}
	
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> M >> N >> K;
	
	for(int i = 0; i < K; i++){
		cin >> x1 >> y1 >> x2 >> y2;
		
		for(int x = x1; x < x2; x++){
			for(int y = y1; y < y2; y++){
					arr[y][x] = 1;
			}
		}
	}
	
	for(int i = 0; i < M; i++){
		for(int j = 0; j < N; j++){
			if(arr[i][j] != 1 && visited[i][j] == 0){
				ret.push_back(DFS(i, j));
			}
		}
	}
	
	sort(ret.begin(), ret.end());
	cout << ret.size() << "\n";
	for(auto i : ret) cout << i << " ";
	
  return 0;    
}

문제만 읽었을 때는 그림 2에 나온 것처럼 나눠진 각 영역의 개수, 영역마다 몇 개로 구성되어있는지를 오름차순으로 출력하라는 문제라고 이해는 했지만,
진짜 문제는 "어떻게 코드로 구현하지" 였다. (그래서 이번에도 역시 답 찾아보고 풀었다. ㅋㅋㅋ)

먼저 예제 입력을 살펴보면

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

M, N, K 순서로 들어오고
K번 만큼 x1, y1, x2, y2 좌표 값이 들어온다.
즉, (0, 2) 부터 (4, 4), (1, 1) ~ (2, 5), (4, 0) ~ (6, 2) 구간이 색칠된 모눈종이라는 것인데 색칠된 부분 = 배열의 값을 1로 지정하기로 했다.

y와 x가 이미지에 표시한 것처럼 좌측 상단에서 시작해야할 것 같은데 일단 좌측 하단이 (0, 0) 이라는 부분에서 또 혼란스러웠었다. ㅋㅋ

그래서 90도로 돌려서도 생각해봤는데 내가 머리가 안좋은지 아무 생각이 안나......

문제를 어떻게 풀지 이해는 못한 상태로 영역 개수 세야되고 몇갠지 세야되니까 DFS로 가보기로 했다.

int DFS(int y, int x){
	visited[y][x] = 1;
	int ret = 1;
	
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		if(ny < 0 || nx < 0 || ny >= M || nx >= N || visited[ny][nx] == 1) continue;
		if(arr[ny][nx] == 1) continue;
		ret += DFS(ny, nx);
	}
	
	return ret;
}

dfs에서 방문 처리하고 오버플로우 체크까지 해줬는데 재귀하는 부분에서 ret 값을 1씩 증가시켜줘야하는구나..를 배웠다. 이 문제는 DFS 함수에서 리턴 값도 필요하다는 것도ㅎㅎ

for(int i = 0; i < M; i++){
	for(int j = 0; j < N; j++){
		if(arr[i][j] != 1 && visited[i][j] == 0){
			ret.push_back(DFS(i, j));
		}
	}
}

sort(ret.begin(), ret.end());
cout << ret.size() << "\n";
for(auto i : ret) cout << i << " ";

아직 방문 안했고 색칠된 부분이 아닌 경우엔 DFS를 호출해줘야 한다.
여기서 벡터 ret에 push하는 이유는 영역의 넓이를 오름차순으로 출력해주어야 하기 때문이다.

지금보니까 변수 이름을 다소 헷갈리게 해놨는데 DFS 함수 내부에서 카운트하는 변수가 있고 여기서 vector로 선언한 ret이 있다.

출력은 오름차순으로 하라고 했으니 vector 오름차순 정렬시키고 현재 영역의 개수인 vector의 size와 반복문을 통해 하나씩 출력해주면 된다.

일주일 뒤 내가 다시 풀어볼 문제.......