✅ BFS ✅ 연결요소

문제

링크

풀이

1. 문제 접근

사각형들이 왼쪽 아래 꼭짓점과 오른쪽 위 꼭지점 두개의 좌표로 주어진다는 것 뿐,
이전에 풀었던 2667 단지번호붙이기와 동일한 문제이다.

2. 자료구조 or 알고리즘 선택과 그 이유

연결요소 구하기 문제이므로 DFS, BFS 모두 가능하다.
바로 이전에 BFS로 풀었으니 이번에는 DFS로 풀어보자

3. 문제 해결 로직 (풀이법)

편의상 모눈종이 한칸의 중심을 좌표로 생각하자.
무슨 소리냐면, 아래 그림처럼 사각형(모눈종이 한칸)의 중심을 사각형 왼쪽 아래로 가져와 좌표축 위에 오도록하자는 말이다.
그러면 모눈종이 한칸의 영역이 차지되어 있는지 없는지 좌표로 알 수 있다.

주의해야 할점은, 한칸에 한칸에 좌표 하나씩 대응시켜보면 마지막 칸도 왼쪽 아래 좌표에 대응되므로 좌표의 최대가 (0,5)가 아니라 (0,4)가 된다.

따라서 사각형이 {0 2 4 4}로 주어지면 오른쪽 위 꼭지점인 (4,4)만 (3,3)으로 바꾸어 좌표를 표시해주면 된다.

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int M, N, K;
bool map[101][101];
bool visited[101][101];
int cnt = 0;
vector<int> area;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void DFS(int y, int x)
{
    cnt++;
    visited[y][x] = true;

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

        if (nx < 0 || nx >= M || ny < 0 || ny >= N)
            continue;

        if (map[ny][nx] == false && visited[ny][nx] == false)
        {
            DFS(ny, nx);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> M >> N >> K;
    for (int i = 0; i < K; i++)
    {
        int x1, y1, x2, y2; // 왼쪽 아래 꼭지점 (x1, y1), 오른쪽 위 꼭지점 (x2, y2)
        cin >> x1 >> y1 >> x2 >> y2;

        for (int x = x1; x < x2; x++) // 오른쪽 위 꼭지점 (x2, y2) 은 map에 포함하지 않음 (이유는 풀이법 참고)
        {
            for (int y = y1; y < y2; y++)
            {
                map[x][y] = true; // 사각형 영역
            }
        }
    }

    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < M; y++)
        {
            if (map[x][y] == false && visited[x][y] == false){ // 사각형 영역이 아닌곳만 이동 가능 (map[x][y] == false)
                cnt = 0;
                DFS(x, y);
                area.push_back(cnt);
            }  
        }
    }

    sort(area.begin(), area.end());

    cout << area.size() << "\n";
    for (int i = 0; i < area.size(); i++)
    {
        cout << area[i] << " ";
    }
    cout << "\n";

    return 0;
}

4. 시간 복잡도 분석

O(n^2)
(n은 정점의 개수)

5. 문제에서 중요한 부분

사각형 영역을 좌표로 변환하는게 중요한 문제였다.
그과정에서 범위가 줄어든다는 것을 간과했다면 어려웠을 문제
이문제는 처음부터 그림을 그려가며 이해해서 바로 알 수 있긴 했지만

머리로만 예측하지 말고 직접 경우를 손으로 그려보고 검증하는게 중요하다는 걸 느낀 문제

🔥 error

처음에 풀이코드와 반대로 사각형 영역을 받기 전에 map을 모두 true로 해놓고 사각형 영역을 false로 받았었는데 답이 틀리게 나왔었음
아마 영역을 좌표로 옮기는 과정에서 true, false가 꼬인거 같음

연산을 여러개 하는 경우에는 내가 예상하지 못한 결과, 혹은 경우의 수가 나올 수도 있으므로 최대한 복잡하지 않게 알고리즘을 구성하는게 좋을 것 같다.
내가 예상하는대로(?) 나올 수 있게