[BaekJoon] 2583번 - 영역 구하기 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 모눈종이에서 직사각형 내부를 제외한 분리된 영역의 개수와 영역의 넓이를 오름차순으로 구하는 문제로 BFS를 활용하면 간단하게 해결할 수 있다. 주어진 모눈종이를 시계방향으로 90도 회전했다고 생각하면 행이 $N$, 열이 $M$ 인 2차원 배열로 생각할 수 있으며, 직사각형이 차지하는 위치를 마킹하고 마킹되지 않은 영역에 대해 BFS로 넓이를 구하고 개수를 카운팅하면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean[][] map = new boolean[N][M];
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int sr = Integer.parseInt(st.nextToken());
            int sc = Integer.parseInt(st.nextToken());
            int er = Integer.parseInt(st.nextToken());
            int ec = Integer.parseInt(st.nextToken());

            for (int r = sr; r < er; r++) {
                for (int c = sc; c < ec; c++) {
                    map[r][c] = true;
                }
            }
        }

        int cnt = 0;
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!map[i][j]) {
                    int result = bfs(i, j, N, M, map);
                    cnt++;
                    list.add(result);
                }
            }
        }
        list.sort(Comparator.naturalOrder());

        sb.append(cnt).append("\n");
        for (int x : list) {
            sb.append(x).append(" ");
        }

        System.out.println(sb);
    }

    static int bfs(int sr, int sc, int n, int m, boolean[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sr, sc});

        map[sr][sc] = true;

        int cnt = 1;

        while (!q.isEmpty()) {
            int[] node = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = node[0] + dr[d];
                int nc = node[1] + dc[d];

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (map[nr][nc]) continue;

                q.add(new int[]{nr, nc});
                map[nr][nc] = true;
                cnt++;
            }
        }

        return cnt;
    }
}

2. 풀이 [C++]

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

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int n, m, k;
bool grid[100][100];

int bfs(int sr, int sc) {
    queue<pair<int, int>> q;
    q.push({sr, sc});

    grid[sr][sc] = true;

    int cnt = 1;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc]) continue;

            q.push({nr, nc});
            grid[nr][nc] = true;
            cnt++;
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> k;

    for (int i = 0; i < k; i++) {
        int sr, sc, er, ec;
        cin >> sr >> sc >> er >> ec;

        for (int r = sr; r < er; r++) {
            for (int c = sc; c < ec; c++) {
                grid[r][c] = true;
            }
        }
    }

    int cnt = 0;
    vector<int> v;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!grid[i][j]) {
                int res = bfs(i, j);
                cnt++;
                v.push_back(res);
            }
        }
    }
    sort(v.begin(), v.end());

    cout << cnt << '\n';
    for (int x : v) {
        cout << x << ' ';
    }
}

---