백준 2583번 영역구하기 자바 풀이 및 정답

백준 2583번 영역구하기 문제 설명

표가 주어지며 직사각형 형태의 좌표가 주어집니다. 해당 좌표를 제외하고 각각의 영역의 넓이를 구하는 문제입니다.

 

각 영역을 탐색해서 넓이를 구해야 한다는 부분에서 DFS를 떠올릴 수 있지만 가로, 세로의 영역이 좌표처럼 주어진다는 부분과 좌표에서 특정 영역을 제외해야한다는 부분을 어떻게 풀어나갈 지가 중요한 문제라고 볼 수 있습니다. 저의 경우 DFS를 돌 떄 익숙하게 돌기 위해서 표를 뒤집는 방법을 적용했습니다.

 

0123

백준 2583번 영역구하기 그림 설명

그림1 - for문을 더 직관적으로 돌기 위해서 상하반전을 시켜줍니다. 이렇게 하면 평소 자주 도는 for문 형태와 같아집니다.

그림2 - for문을 돌 때 좌표 형태가 어떻게 그려지는 확인합니다. 문제에서 주어지는 직사각형 좌표값을 어떻게 대입하면 정확히 좌표상에 일치하는지 확인 가능합니다.

그림3 - DFS 방식으로 탐색을 해나갑니다. 이때 입력받은 직사각형은 -1과 같이 별도로 구분해 해당 영역은 탐색하지 않도록 해야합니다. DFS를 끝마치면 그림4와 같은 그림이 되도록 진행합니다.

 

 

백준 2583번 영역구하기 정답 코드(자바)

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

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visitedArray;
    static int cnt;
    public static void main(String[] args) throws IOException{
        BufferedReader brd = new BufferedReader(new InputStreamReader(System.in));
        int m, n, k;
        String[] a = brd.readLine().split(" ");
        m = Integer.parseInt(a[0]); // i변수
        n = Integer.parseInt(a[1]); // j변수
        k = Integer.parseInt(a[2]); // 좌표값

        int[][] board = new int[m][n];
        visitedArray = new boolean[m][n];
        for (int z=0; z<k; z++) {
            String[] b = brd.readLine().split(" ");
            int jStart = Integer.parseInt(b[0]);
            int iStart = Integer.parseInt(b[1]);
            int jEnd = Integer.parseInt(b[2]);
            int iEnd = Integer.parseInt(b[3]);

            for (int i=iStart; i<iEnd; i++) {
                for (int j=jStart; j<jEnd; j++) {
                    board[i][j] = -1;
                }
            }
        }

        ArrayList<Integer> answerArray = new ArrayList<>();
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (visitedArray[i][j] || board[i][j] == -1) continue;
                cnt = 0;
                DFS(board, i, j);
                answerArray.add(cnt);
            }
        }

        Collections.sort(answerArray);
        StringBuilder sb = new StringBuilder();
        sb.append(answerArray.size());
        sb.append("\n");
        for (int x : answerArray) {
            sb.append(x);
            sb.append(" ");
        }
        System.out.println(sb);
    }

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

        for (int i=0; i<dx.length; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length) continue;
            if (board[nx][ny] == -1 || visitedArray[nx][ny]) continue;
            DFS(board, nx, ny);
        }
    }
}