[백준][Java] 2583번 : 영역 구하기

[문제 링크]

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

---

문제 설명

눈금의 간격이 1인 M×N 크기의 모눈종이 위에 K개의 직사각형을 그릴 때, K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 M, N, K
• 둘째줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 두 꼭짓점의 x, y값(직사각형의 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점)

출력

• 분리되어 나눠지는 영역의 개수
• 각 영역의 넓이

입출력 예시

• 입력예시	출력예시
  5 7 3 0 2 4 4 1 1 2 5 4 0 6 2	3 1 7 13

 

 

 

문제 풀이

• dfs 알고리즘 사용
• 입력받은 직사각형 영역 안에 포함되는 칸을 1, 나머지 부분은 0 으로 처리
• dfs로 상,하,좌,우로 탐색하면서 0인 부분을 찾아 분리된 영역들의 각각 넓이 구한다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static int m, n, k;
    public static int size = 0;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static int[][] map;
    public static ArrayList<Integer> result = new ArrayList<>();

    public static boolean dfs(int x, int y) {

        //주어진 모눈종이 영역을 벗어나면 종료
        if (x < 0 || y < 0 || x >= m || y >= n) {
            return false;
        }

        if (map[x][y] == 0) {
            map[x][y] = 1;  //방문 처리
            size++;

            //상, 하, 좌, 우으로 방문
            dfs(x - 1, y);
            dfs(x + 1, y);
            dfs(x, y - 1);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }

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

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new int[m][n];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            //직사각형에 포함된 영역을 1로 초기화
            for (int y = y1; y < y2; y++) {
                for (int x = x1; x < x2; x++) {
                    map[y][x] = 1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j) == true) {
                    result.add(size);
                    size = 0;
                }
            }
        }
        System.out.println(result.size());

        //오름차순 정렬 후 출력
        Collections.sort(result);
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }
}

 

✔️문제를 읽자마자 이코테에서 풀었던 '음료수 얼려먹기' 가 생각나서 이와 같은 방식으로 풀었다. 아직 DFS/BFS 중 어떤 알고리즘을 써야할지 조금 헷갈리는 것 같다🥲