[백준 2583] 영역구하기_bfs(C++)

1.문제

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

2.접근방법

1. bfs로 영역을 나눠야 겠다고 바로 생각!(게리맨더링이랑 비슷하다고 생각했다)
2. 탐색시작점이 따로 없으니, 어디서부터 시작할지 고민했음
3. 첫번째 영역의 탐색이 끝나고 나면(이동하면서 막혀서 더이상 이동할 수 없을때 영역이 정해짐) , 다음영역으로 어떻게 시작점이 넘어가야하는지 좋은 방법이 떠오르지 않음
4. 결국 모든 점을 방문할 수 밖에 없겠다는 결론이 내려짐 ㅠ
5. 한 점에서 시작 -> 큐가 비워짐 -> 첫번째 영역이 구해짐 -> 벡터에 넣는다
6. 결국 벡터의 사이즈는 영역의 갯수가 됨
7. 영역들의 넓이는 벡터 for문 돌면서 출력하면 됨

3.문제풀이

1. 입력으로 주어진 사각형(넓이부분 전체 다 )을  map을 1로 만들어준다.(bfs를 돌면서 접근하지 못하도록 하기 위해) -> 방문체크의 역할을 하는것임. 
2. 2차원이니 2중for문을 돌면서 bfs를 호출한다. 단, 아래의 조건 밑에서 호출해야만 한 정점을 여러번 방문하는 것을 막을 수 있다.) 
3. bfs함수에서 while문을 들어가기전에 매개변수로 넘겨진 x,y를 큐에 넣어주고, 그 정점의 방문체크를 해준다. 처음 시작은 무조건 1이다. 각 영역의 첫번째 시작이므로..!!
4. while문을 돌면서 cnt++되면서 넓이가 구해지게 될것이다.
5. 결국 마지막에 도달하는 지점에서 저장된 cnt의 값이 해당 영역의 넓이이다. 
6. while문을 빠져나오게 되면 vector에 cnt값을 넣어준다.
7. 각 영역의 넓이를 다 구해주고 오름차순으로 넓이를 출력하라고 했으므로 벡터 안의 값을 sort해준다.
8. 벡터의 사이즈와, 벡터값을 출력해주면 끝

if (map[i][j] == 0 && group[i][j] == 0) { //group이 방문체크의 역할을 한다.
                bfs(i, j);
}

 

4.전체코드

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, k;
struct Pos {
    int x; int y;
};
int map[101][101];
int group[101][101];
 
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
queue<Pos> q;//bfs돌때 각 영역(서로 접해져있는 곳까지의 영역)을 탐색하기 위해 좌표를 넣기위한 큐
vector<int> v_ans;//영역의 갯수와, 영역의 넓이를 받아놓기 위한 벡터
 
void bfs(int x, int y) {
    int cnt = 1; //시작을 1로 해주어야, (0.0)만 map==0 일때 1로 셀 수 있음
    q.push({ x,y });
    group[x][y] = cnt; //main함수에서 이중포문으로 받아온 x,y 위치를 해당 영역의 몇번째 칸인지 cnt로 구분.
 
    while (!q.empty()) {
        x = q.front().x;
        y = q.front().y;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
                if (map[nx][ny] == 0 && group[nx][ny] == 0) {
                    q.push({ nx, ny });
                    cnt++;
                    group[nx][ny] = cnt;//cnt로 영역을 센ㄷㅏ.
                }
            }
        }
    }
    v_ans.push_back(cnt);//while문을 나오게되면 cnt의 값이 결국 한 영역의 넓이값이 된다.
}
 
int main() {
    cin >> m >> n >> k; //행과 열
 
    for (int i = 0; i < k; i++) { //사각형 영역을 1로 주기.
 
        int startX, startY, endX, endY;
        cin >> startX >> startY >> endX >> endY;
 
        for (int j = startX; j < endX; j++) {
            for (int t = startY; t < endY; t++) {
                map[t][j] = 1;//주어진 사각형을 1로 만들어준다.
            }
        }
    }
 
    //bfs로 영역 구하기 -> 영역을 구하려면 어쩔수없이 모든 map을 다 돌아봐야함
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 0 && group[i][j] == 0) { //group이 방문체크의 역할을 한다.
                bfs(i, j);
            }
        }
    }
    sort(v_ans.begin(), v_ans.end());// 정렬해서 출력하라고 했으므로
    
    cout << v_ans.size() << "\n";//벡터의 사이즈 = 영역의 갯수
    
    for (int i = 0; i < v_ans.size(); i++) {
        cout << v_ans[i] << " ";
    }
    return 0;
}