백준 알고리즘 2583번 문제 - 영역 찾기(c++)

문제 풀러가기

2583번: 영역 구하기

문제 설명

이 문제는 지난 번 2468 문제와 같이 dfs를 사용하여 Connected Component(연결 요소)의 수를 파악하는 문제이다. 연결 요소의 수 뿐만 아니라 각 연결 요소의 너비도 함께 구해줘야 한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

const int max_n = 101;
int m, n, k, ux, uy, hx, hy, a[max_n][max_n], visited[max_n][max_n];
vector<int> v;
int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1};

int dfs(int y, int x) {
    visited[y][x] = 1;
    int ret = 1;

    for(int i=0; i<4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
        if(!a[ny][nx] && !visited[ny][nx]) ret += dfs(ny, nx);
    }
    return ret;

}

int main() {

    // 2차원 배열의 열의 수, 행의 수, 직사각형의 수 입력받기
    cin>>m>>n>>k;

    // 직사각형의 수만큼 좌표 입력받기
    while(k--) {
        cin >> ux >> uy >> hx >> hy;

        for(int i=uy; i<hy; i++) {
            for(int j=ux; j<hx; j++) {
                a[i][j] = 1;
            }
        }
    }

    // 2차원 배열 방문하여 Connected Component 찾기
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(!a[i][j] && !visited[i][j]) {
                // 반환받은 ret(연결 영역의 너비)을 v에 저장
                v.push_back(dfs(i, j));
            }
        }
    }

    // 나머지 영역의 수
    cout << v.size() << '\n';

    // 영역의 너비 정렬
    sort(v.begin(), v.end()); 

    // 영역별 너비 출력
    for(int i : v) {
        cout << i << ' ';
    }

    return 0;

}

풀이

1. 배열의 높이(m), 너비(n), 직사각형의 개수(k)를 입력 받아 각 변수에 대입한다.
2. 직사각형의 수만큼 좌표를 입력 받아 1로 채워준다
   • ex) (0, 2), (4, 4)의 경우 x좌표 0~4, y좌표 2~4 까지 반복문을 돌려 값을 1로 바꿔준다.
3. 2차원 배열 각 원소 중 값이 없고(== 0) 방문하지 않은 원소에 방문한다.
   • 연결 요소의 영역을 모두 탐색하고 나면 연결요소의 영역 너비(ret)를 vector에 담아준다
4. 연결 요소(영역)의 수(v.size())와 각 영역의 너비를 오름차순으로 정렬하여 출력한다.

주의할 점

• dfs가 int형 변수 ret을 반환하는 방식
• M이 배열의 높이, N이 배열의 너비를 담당하기 때문에 배열에 접근할 때 헷갈리지 않도록 한다.
• #include <bits/stdc++.h>을 사용할 경우 y1이라는 변수를 사용할 수 없으니 주의! 만약 y1을 사용하고 싶다면 #define y1 aaaa 이런 식으로 정의 해주어야 한다.