백준 2583 영역 구하기 c++ [컴공과고씨]

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

2583번: 영역 구하기

문제를 보면 탐색 유형의 문제임을 알 수 있다.

보고 든 풀이 방법은 색칠 된 부분을 visit[][]에 방문 기록을 해 준 후 반복문을 통해 방문하지 않은 좌표를 bfs에 넣어준다. 그렇게 해서 bfs가 실행된 횟수가 나눠진 영역의 수이고 영역의 넓이는 bfs 함수를 구현 할 때 다음 좌표로 탐색할때 카운트를 해주고 bfs가 종료되었을 때 vector에 넣어 저장해주고 출력하기전에 sort를 하여 오름차순으로 출력해주면 해결이 된다.

 

중요한건 색칠된 부분을 표현해주는 방법인데 주어진 좌표가 배열과는 다른 좌표로 이루어져 있어 좌표를 좀 변환해 주었다. 나는 행렬순으로 표현해서 (row,col) 이 좌표로 바꾸어 주었다. 문제 좌표에서 (0,2)로 주어지고 그 다음 (4,4)로 주어진다면 내가 만든 행렬에서의 좌표는 높이 row는 2부터 3까지, col은 0부터 3까지이다. 

보면 입력에서 주어진 좌표에서 그 다음 좌표까지 이중 포문을 돌려준다. 이렇게 하면 주석에도 써있듯이 상하가 바뀌게 되지만 영역의 넓이와 개수는 변하지 않기 때문에 상관이없다. 계산을 통해 위 문제처럼 좌표를 정확하게 맞추어 줄 수도 있지만 굳이 그럴 필요는 없다. 문제에 푸는데에는 지장이 없음.

이렇게 좌표환산을 해서 visit에 방문 처리 해주고 bfs 구현 해주면 끝이난다.

 

전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int m, n, k, a, b, c, d;
int ans = 0;
bool visit[101][101];
vector<int> area;
 
void bfs(int a1, int b1){
    queue<pair<int, int>> q;
    q.push(make_pair(a1, b1));
    visit[a1][b1] = true;
    int cnt = 1;
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4;i++){
            int n_x = x + dx[i];
            int n_y = y + dy[i];
            if (n_x < n && n_x >= 0 && n_y < m && n_y >= 0){
                if(!visit[n_y][n_x]){
                    q.push(make_pair(n_y, n_x));
                    visit[n_y][n_x] = true;
                    cnt++; //영역넓이 + 1
                }
            } 
        }
    }
    area.push_back(cnt);
}
int main(){
    cin >> m >> n >> k;
    for (int i = 0; i < k;i++){
        cin >> a >> b >> c >> d;
        for (int r = b; r < d;r++){ // 좌표를 환산 
            for (int l = a; l < c;l++){ // 좌표를 환산
                visit[r][l] = true; //색칠 된 부분은 방문처리
            }
        }
    }// 위 좌표는 보기 편하게 바꾼 것으로 저렇게 하면 상하가 바뀌지만
    //영역의 수와 넓이는 바뀌지 않기 때문에 상관없음
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n;j++){
            if(!visit[i][j]){ 
                bfs(i, j);
                ans++; //bfs 실행 횟수가 영역의 수
            }
        }
    }
    cout << ans << '\n';
    sort(area.begin(), area.end());
    for (int i = 0; i < area.size(); i++){
        cout << area[i] << " ";
    }
        return 0;
}

 

사용 문법 : bfs

 

yea!