[BOJ 2583] 영역 구하기 (Java)

문제

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

2583번: 영역 구하기

 

풀이

좌표 영역을 칠하고, DFS로 빈 공간의 개수와 넓이를 구한다. 

영역 칸의 개수를 구해야 하기 때문에, 입력된 좌표를 그대로 사용하면 정확한 답을 구할 수 없다.-

이를 해결하기 위해, 칠할 영역 시작 좌표의 x, y 좌표는 +1을 해주어서 좌표의 기준을 우측 대각선 위로 동일하게 맞춰주었다.

ex) 칠해야 할 영역의 시작 좌표가 0, 0 일 경우 1, 1로 변경해서 칠한다.

 

소스코드

package dfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class BOJ2583 {
    static int M, N, K, size;
    static int[][] map;
    static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        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[N+1][M+1];
        for(int i = 0; i < K; i++){
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken()) + 1;
            int sy = Integer.parseInt(st.nextToken()) + 1;
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());

            for(int x = sx; x <= ex; x++){
                for(int y = sy; y <= ey; y++){
                    map[x][y] = 1;
                }
            }
        }

        ArrayList<Integer> answer = new ArrayList<Integer>();
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(map[i][j] == 0){
                    size = 0;
                    dfs(i, j);
                    answer.add(size);
                }
            }
        }
        System.out.println(answer.size());
        Collections.sort(answer);
        StringBuilder sb = new StringBuilder();
        for(int n : answer){
            sb.append(n + " ");
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int x, int y){
//        System.out.println(x+", "+y);
        map[x][y] = 1;
        size++;
        for(int[] d : dir){
            int nx = x + d[0];
            int ny = y + d[1];
            if(isValid(nx, ny)){
                dfs(nx, ny);
            }
        }
    }

    public static boolean isValid(int nx, int ny){
        if(nx < 1 || ny < 1 || nx > N || ny > M) return false;
        if(map[nx][ny] == 1) return false;
        return true;
    }
}