백준, BOJ, 2583번 C++ [CPP] **

 

이 문제도 BFS의 기본적인 문제라고 볼 수 있지만

역시나 BFS를 어렵게 하려면 입력을 이상하게 주면 된다.

 

 

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

2583번: 영역 구하기

 

---

 

이번 풀이의 핵심은

BFS가 아니다.

 

문제에서 이 사각형의 넓이를 무엇으로 구할 것이냐? 가 문제다.

또한 주어진 조건에 대해서 어떻게 예외처리를 할 것이냐? 가 문제다.

 

우리가 지금 노드의 개수와 사각형의 개수가 1:1 대응하는가?

 

 

 

꼭짓점이 노드라고 한다면 8 * 6 = 48로 

사각형의 개수 35랑 13개나 차이가 난다.

 

아 뭐야 노드를 세는 것이 아닌가?

그럼 어떻게 해야하지???

 

이거에 빠지면 나처럼 1시간 날리는 것이다.

 

이거 저거 예외처리하고 어쩌고 저쩌고

이정도 난이도 문제에서 이거 저거 예외처리 할 것이 많아진다?? 

풀이 방향이 잘못된 것이니 문제를 다시 보는 것이 나의 실수를 반복하지 않는 데 좋다.

 

다시 그림을 보자

 

 

나중에 깨달은 것이지만 이 깨달음을 안다면 다른 문제에도 적용할 수 있겠다.

 

빨간 점을 보자. 사각형 2개가 지금 공유하고 있다.

파란 점을 보자 사각형 1개만 점유되어 있다.

 

즉, 파란 점으로 저 사각형을 대표할 수 있는가?

 

왼쪽 아래 점의 개수를 센다면 사각형의 개수와 같아짐을 알 수 있다.

즉, 여기선 실제로 5까지의 범위지만 사각형이 주어진다면 4까지의 범위로 작아짐을 알 수 있다.

노드는 각개로 존재하지만 사각형을 공유하는 점이 생기기 때문이다.

 

이걸 깨달아야... 나중에도 잘 풀 것이다.

난 이걸 한 시간 걸렸으니 잊지 말아야겠다.

 

---

 

#1 맞는 풀이

#include <iostream>
#include <queue>
#include <algorithm>

#define X first
#define Y second


using namespace std;

//0초기화
int map[101][101];
int vis[101][101];

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

int M,N,K ;

int cnt = 0; // 나눠진 개수

    
void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    init();
    
    vector<int> ans; // 각 넓이를 넣을 곳
    
    cin >> M >> N >> K; // M=y N=x
        
    // 3번 입력 받음    
    while(K--){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        //항상 오른쪽 위에 있는 좌표가 더 큼
        for(int i = x1; i<x2; i++){
            for(int j = y1; j<y2; j++){
                map[i][j] = 1;
            }
        }
    }
    
    
    //입력 받고난 뒤 모든 좌표를 뒤져서 조사
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            
            if(map[i][j] == 1 || vis[i][j] == 1){
                continue;
            }
            
            // 반복문 돌 때 마다 큐를 초기화시킴
            queue<pair<int,int>> Q;
            
            Q.push({i,j});
            vis[i][j] = 1;
            int width = 1; // 반복문 돌 때 마다 넓이 초기화
            cnt++; // 시작 노드 개수 == 나눠진 영역
            
            while(!Q.empty()){
                auto cur = Q.front();
                Q.pop();
                
                for(int dir = 0; dir<4; dir++){
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                     //범위
                    if(nx<0 || nx >= N || ny < 0 || ny >= M){
                        continue;
                    }
                    //이미 방문했거나 사각형을 막혀있는 경우
                    if(map[nx][ny] == 1 || vis[nx][ny] == 1){
                        continue;
                    }
                
                    //범위를 벗어나지 않고 방문할 수 있으면서 아직 안한 경우
                    Q.push({nx,ny});
                    vis[nx][ny] = 1;
                    width++;
                }
            }
            ans.push_back(width);
        }
    }
    
    // vector에 들어간 값 sort
    sort(ans.begin(), ans.end());
    
    cout << cnt << "\n";
    
    for(int v : ans){
        cout << v << " ";
    }
    
    
    
}