[BaekJoon/백준] 2583번 영역 구하기

 

19시에 자버렸고,, 22:30분에 눈을 떴다.. 생활패턴 망했네.

 

 

이 문제를 풀 땐, x축 기준으로 뒤집어서 배열 상으로 생각하여 풀었다.

시간복잡도는 dfs => O(n) x n^2 = O(n^3) 정도 나오는데, 사실 이정도는 안나올 것 같다.

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

using namespace std;

int Arr[100][100];
int N, M, K;

int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};

int COUNT;
vector<int> T;
int T_SIZE;

void dfs(int x, int y) {
    
    Arr[x][y] = 1;
    COUNT++;
    
    int xx, yy;
    
    for(int i = 0; i < 4; i++) {
        xx = x + mx[i];
        yy = y + my[i];
        
        if(xx < 0 || xx >= N || yy < 0 || yy >= M)
            continue;
        
        if(Arr[xx][yy] == 0)
            dfs(xx, yy);
    }
    
}

int main() {
    
    int sx, sy, ex, ey;
    
    cin >> N >> M >> K;
    
    // 예시 그림을 x축 대칭으로 뒤집어서 생각. 배열상으로.
    
    for(int i = 0; i < K; i++) {
        
        cin >> sy >> sx >> ey >> ex; // 입력을 이렇게 변환
        
        
        for(int i = sx; i < ex; i++) {
            
            for(int j = sy; j < ey; j++) {
                
                Arr[i][j] = 1;
            }
        }
    }
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            if(Arr[i][j] == 0) {
                COUNT = 0;
                dfs(i, j);
                T.push_back(COUNT);
            }
        }
    }
    
    
    sort(T.begin(), T.end());
    cout << (T_SIZE = T.size()) << "\n";
    
    for(int i = 0; i < T_SIZE; i++)
        cout << T[i] << " ";
    
    
}