[백준] 2583 | 영역 구하기 | C++

풀이 전에,

선을 기준으로 한 좌표체계를 공간으로 바꾸는 방법은 의외로 간단하다.

오른쪽 위 꼭지점 좌표를 end포인터처럼 생각하면 된다.

(소스코드의 input함수 참고)

그러면 아래 그림의 좌표체계를 선이 아닌, 공간처럼 인식할 수 있다.

 

---

 

1. DFS 풀이

 

DFS 풀이의 핵심은 이렇다.

 

int 영역넓이(전역변수);

풀이함수(solution)에서 좌표마다 반복:
    만약 빈 좌표라면:
        DFS를 돌린다(빈 좌표갯수 count, 인접한 빈 좌표들을 채운다);
        반환값1(영역갯수)++;
        영역넓이를 반환값2에 저장한다;
        영역넓이를 0으로 초기화한다;

void DFS(좌표):
    현재 좌표를 채운다;
    영역넓이++;
    4방향반복:
        만약 togo좌표가 비어있다면:
            DFS(togo좌표) 재귀진입;

 

각 영역마다의 넓이를 전역변수로 설정하였다.

DFS는 그저 빈 좌표의 갯수를 count해주는 함수라고 생각하면 쉽다.

즉, DFS가 진행되는동안 넓이는 전역변수로써 더해지는 것이다.

그리고 DFS가 끝나면 영역넓이를 반환값2에 저장한다.

전역변수이기 때문에 다음 영역의 넓이를 구하기 위해서 0으로 초기화도 해주어야 한다.

 

DFS 프레임 내에서 넓이를 구해서 저장하는 방식보다 훨씬 정확하고 간단한 방법이다.

 

특이하게도, 기저조건을 따로 설정할 필요는 없었는데,

DFS를 끝낼 만한 특별한 조건같은 것도 없고,

DFS가 실행되기 전에 먼저 비어있는지 check를 하도록 했기 때문이다.

('선조건방식'이라고 해도 될지 모르겠다.)

 

---

 

정답 소스코드

 

#include<bits/stdc++.h>
using namespace std;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1}; 

int arr[104][104];

int n, m, k;
int sx, sy, ex, ey;

int area; //영역 넓이

int res1;
vector<int> res2;

void DFS(int y, int x);

void input() {
    cin>>n>>m>>k;
    while(k--) {
        cin>>sx>>sy>>ex>>ey;
        for(int i=sy; i<ey; i++) {
        for(int j=sx; j<ex; j++) {
            arr[i][j]=1;
        }}
    }
}

void solution() {
    for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
        if(arr[i][j]==0) {
            DFS(i, j);
            res1++;
            res2.push_back(area);
            area=0;
        }
    }}
}

void DFS(int y, int x) {
    arr[y][x]=1;
    area++;
    for(int i=0; i<4; i++) {
        int ny=y+dy[i];
        int nx=x+dx[i];

        if(ny<0 || nx<0 || ny>=n || nx>=m) continue;

        if(arr[ny][nx]==0) DFS(ny, nx);
    }
}

void output() {
    cout<<res1<<"\n";
    sort(res2.begin(), res2.end());
    for(int i=0; i<res1; i++) cout<<res2[i]<<" ";
    cout<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    output();
    return 0;
}

 

---

 

2. BFS 풀이

 

BFS 풀이의 핵심은 이렇다.

 

int 영역넓이(전역변수);

풀이함수(solution)에서 좌표마다 반복:
    만약 빈 좌표라면:
        BFS를 돌린다(빈 좌표갯수 count, 인접한 빈 좌표들을 채운다);
        반환값1(영역갯수)++;
        영역넓이를 반환값2에 저장한다;
        영역넓이를 0으로 초기화한다;

void BFS(좌표):
    현재 좌표를 채운다.
    영역넓이++;
    queue에 현재 좌표를 push한다.
    
    queue가 빌 때까지:
    	좌표를 꺼낸다;
        꺼낸 좌표를 기준으로 4방향 반복:
        	만약 togo좌표가 비어있다면:
            		togo좌표를 채운다.
                    	영역넓이++;
            		BFS에 togo좌표 push;

 

 

BFS도 그저 빈 좌표를 count해나가는 방식이다.

BFS프레임 내에서 queue에 좌표를 push할 때마다

전역변수로 설정한 영역넓이가 더해지는 것이다.

물론, 다음 영역의 넓이를 구하기 위해서 0으로 초기화도 해주어야 한다.

 

---

 

정답 소스코드

 

#include<bits/stdc++.h>
using namespace std;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1}; 

int arr[104][104];

int n, m, k;
int sx, sy, ex, ey;

int area; //영역 넓이

void BFS(int y, int x); 

int res1;
vector<int> res2;

void input() {
    cin>>n>>m>>k;
    while(k--) {
        cin>>sx>>sy>>ex>>ey;
        for(int i=sy; i<ey; i++) {
        for(int j=sx; j<ex; j++) {
            arr[i][j]=1;
        }}
    }
}

void solution() {
    for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
        if(arr[i][j]==0) {
            BFS(i, j);
            res1++;
            res2.push_back(area);
            area=0;
        }
    }}
}

void BFS(int y, int x) {
    queue<pair<int, int> > Q;

    arr[y][x]=1;
    area++;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        int curY=Q.front().first;
        int curX=Q.front().second;
        Q.pop();

        for(int i=0; i<4; i++) {
            int ny=curY+dy[i];
            int nx=curX+dx[i];

            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;

            if(arr[ny][nx]==0) {
                arr[ny][nx]=1;
                area++;
                Q.push(make_pair(ny, nx));
            }
        }
    }
}

void output() {
    cout<<res1<<"\n";
    sort(res2.begin(), res2.end());
    for(int i=0; i<res1; i++) cout<<res2[i]<<" ";
    cout<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    output();
    return 0;
}