[그래프 / BOJ 2583 / C++] 영역 구하기

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

2583번: 영역 구하기

1. 주어진 좌표를 이용해 먼저 MxN 크기의 배열에서 사각형을 색칠한다. (방문표시)
2. 사각형을 색칠하고 나면 MxN 크기의 배열을 순회하며 bfs나 dfs를 해준다. (이때, 영역의 개수를 구한다)
3. bfs나 dfs를 하면서 해당 영역의 넓이를 구해 배열에 추가해준다.
4. 영역의 개수와 sort된 배열을 출력해준다.

이 문제를 풀 때 (N, M)을 보고 가로 길이는 M 세로길이는 N 이구나 하며 계속 착각했었다....

문제를 정확하게 읽자. x좌표는 N y좌표는 M 이다!!!!

 

문제에 나온 그대로를 구현해주면 된다.

 

1. 주어진 좌표를 이용해 먼저 MxN 크기의 배열에서 사각형을 색칠한다. (방문표시)

2. 사각형을 색칠하고 나면 MxN 크기의 배열을 순회하며 bfs나 dfs를 해준다. (이때, 영역의 개수를 구한다)

3. bfs나 dfs를 하면서 해당 영역의 넓이를 구해 배열에 추가해준다.

4. 영역의 개수와 sort된 배열을 출력해준다.

 

이때, 가장 중요한 것은 주어진 좌표를 이용해 사각형을 색칠하는 작업이다.

만약 (0,0)부터 (1,3)까지의 사각형을 구했다 생각해보자. 그렇다면, 

( ) 은 좌표이고, { } 이탤릭체는 배열에 들어갈 모습이다.

이런 모습으로 생각할 수 있다.

(0,0) 부터 (1,3) 까지의 사각형을 색칠한다는 것은 

a[0][0], a[1][0], a[2][0] 로 이해할 수 있다. (배열로 옮겨 bfs를 할 때는 세로축이 첫번째로 온다,)

손으로 그림을 그리면서 확인해보면 이해가 어렵지 않다.

 

여기서 실수를 많이해서 시간이 오래걸렸었다. 

일단은 가로는 "N" 세로는 "M" 이다. 

즉, vis이라는 배열에 좌표를 넣어줄 때는 vis[y좌표][x좌표] 로 해야한다!!

 

추가적으로, 뜬끔없이 변수명을 y3로 한게 보일 것이다.

bits/stdc++.h에서는 y1이라는 변수명을 사용할 수 없다!!! 반드시 기억해둘것!! 

(이걸 몰라서 많이 헤맸었다..)

#include <bits/stdc++.h>

using namespace std;

int N, M, K, x1, y3, x2, y2, res_cnt;
vector<int> area;
int vis[101][101];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> M >> N >> K;
    
    while(K--) {
        cin >> x1 >> y3 >> x2 >> y2;
        int w = x2 - x1;
        int h = y2 - y3;
        
        for(int i = y3 ; i < y3+h ; i++){
            for(int j = x1 ; j < x1+w ; j++){
                vis[i][j]=1;
            }
        }
    }
    
    
    for(int i = 0 ; i < M ; i++){
        for(int j = 0 ; j < N ; j++){
            if(vis[i][j]) continue;
            res_cnt++;
            
            queue<pair<int, int>> Q;
            vis[i][j] = 1;
            Q.push({i, j});
            int x=0, y=0;
            int small_area=1;
            
            while(!Q.empty()){
                tie(y, x) = Q.front(); Q.pop();
                for(int dir = 0 ; dir < 4 ; dir++){
                    
                    int ny = y + dy[dir];
                    int nx = x + dx[dir];
                    
                    if(ny >= M || ny < 0 || nx >= N || nx < 0) continue;
                    if(vis[ny][nx]) continue;
                    
                    small_area++;
                    vis[ny][nx] = 1;
                    Q.push({ny, nx});
                }
            }
            
            area.push_back(small_area);
        }
    }
    
    sort(area.begin(), area.end());
    cout << res_cnt << '\n';
    for(auto i : area) cout << i << ' ';
    
}