[BOJ 2583] 백준 2583 영역 구하기

#문제 해결 방법

DFS와 BFS 둘다 사용 가능할 것으로 예상했고, DFS를 선택해서 풀었다.

1. x1, y1, x2, y2를 입력받을 때 마다, arr에 바로 1로 표시해주었다.
2. 문제에서 주어진 좌표와 똑같이 표현하기 위해서, y좌표는 (n-y2) ~ (n-y1)으로 loop을 돌렸다.
3. DFS를 호출하기전에 block 개수를 0으로 초기화한다.
4. DFS를 호출하고, 호출할 때 마다 block의 갯수와 visit 함수에 true 값을 넣었다.

 

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

using namespace std;

//좌 우 위 아래
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int arr[101][101]={0,};
bool visit[101][101]={false,};


int dfs(int y, int x, int n, int m, int block){
    block+=1;
    visit[y][x]=true;
    for(int i=0; i<4; i++){
        int nowx=x+dx[i];
        int nowy=y+dy[i];

        if(nowx>-1 && nowx<m && nowy>-1 && nowy<n){
            if(visit[nowy][nowx]==false && arr[nowy][nowx] == 0){
                block = dfs(nowy, nowx, n, m, block);
            }
        }
    }

    return block;
}

int main(){
    int n, m, k;
    vector<int> answer;
    cin >> n >> m >> k;

    int x1,y1,x2,y2;

    for (int i = 0; i < k; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;

        for(int y=(n-y2);y<(n-y1);y++){
            for(int x=x1;x<x2;x++){
                visit[y][x]=true;
                arr[y][x]=1;
            }
        }
    }
    
    int block=0;

    for(int i=0; i<n;i++){
        for(int j=0; j<m; j++){
            if(visit[i][j]==false && arr[i][j]==0){
                block=0;
                int ans = dfs(i,j,n,m,block);
                answer.push_back(ans);
            }
        }
    }

    cout<<answer.size()<<endl;
    sort(answer.begin(), answer.end());

    for(int i=0; i<answer.size(); i++){
        cout<<answer[i]<<" ";
    }

    return 0;
}

 

#DFS의 기본만 이해한다면 빠른 시간 내에 짤 수 있는 알고리즘이었다.

 

## 기억해야할 것

#include <algorithm>

sort(arr.begin(), arr.end()); //오름차순 정렬