2583

백준 2583번

Link: 2583번: 영역 구하기

---

문제 설명

기초적인 BFS 문제다.

2차원 배열에 모눈종이를 표시하고, 표시되지 않은 부분들에 대해 BFS를 진행하며 각 영역의 크기와 총 영역 갯수를 구하는 문제.

문제 보기에 좌표가 조금 다르게 표현되어 있어 이를 2차원 배열로 옮기는 과정에서 생각을 좀 했었다.

좌표만 잘 옮기면 무난히 풀 수 있는 문제.

---

정답 코드

//
// Created by Keith_Lee on 22/01/2019.
//

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

int M, N, K;
int result = 0;

int map[100][100];
bool visit[100][100];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

vector<int> areas;

void BFS(int startX, int startY){
    queue<pair<int, int>> Queue;
    Queue.push(make_pair(startX, startY));

    int area = 1;

    while(!Queue.empty()){
        int currentX = Queue.front().first;
        int currentY = Queue.front().second;
        Queue.pop();

        for(int i=0; i<4; i++){
            int nextX = currentX + dx[i];
            int nextY = currentY + dy[i];

            if(nextX >= 0 && nextX < M && nextY >= 0 && nextY < N){
                if(!visit[nextX][nextY] && map[nextX][nextY] == 0){
                    visit[nextX][nextY] = true;
                    Queue.push(make_pair(nextX, nextY));
                    area++;
                }
            }
        }
    }

    result++;
    areas.push_back(area);
}

int main(){
    cin >> M >> N >> K;

    bzero(map, sizeof(map));

    for(int i=0; i<K; i++){
        int startX, startY, endX, endY;

        cin >> startX >> startY >> endX >> endY;

        for(int j=startY; j<endY; j++){
            for(int k=startX; k<endX; k++){
                map[j][k] = 1;
            }
        }
    }

    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            if(!visit[i][j] && map[i][j] == 0){
                visit[i][j] = true;
                BFS(i, j);
            }
        }
    }

    sort(areas.begin(), areas.end());
    cout << result << '\n';
    for(int i=0; i<areas.size(); i++){
        cout << areas[i] << ' ';
    }
    cout << '\n';

    return 0;
}

---