[백준] 2583번 - 영역 구하기 (Java)

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

2583번: 영역 구하기

 

<문제 분석>

1. 입력데이터 스타일이 좀 특이하다. 직사각형의 대각선 꼭지점의 좌표가 2개 주어지는데 입력 받자마자 map에 사각형 넓이만큼 1로 채우자. 그런 다음 탐색을 통해서 빈공간의 갯수와 넓이를 구하면 된다.

for (int i=0; i<K; i++) {             int y1 = in.nextInt();             int x1 = in.nextInt();             int y2 = in.nextInt();             int x2 = in.nextInt();             for (int x=x1; x<x2; x++) {                 for (int y=y1; y<y2; y++) {                     A[x][y] = 1;//좌표의 범위만큼 사각형을 1로 채운다                 }             }         }

2. 사각형이 아닌 곳의 넓이를 구하는 것이니 반대로 0인 곳만 탐색해서 값을 구하면 된다.

3. dfs 파라미터로 좌표 x, y와 이동 count를 넘겨준다. 받으면 즉시 max에 저장하고 다시 dfs 호출 시에는 max+1을 넘겨준다. 왜냐하면 탐색을 다하고 다시 이전 노드로 돌아와서 다른 루트로 탐색을 하기 위해서 stack에 저장된 이전 값을 꺼내면 count가 이전에 저장된 값을 사용하기 때문에 최종값이 틀려지기 때문이다. 그래서 매번 max로 저장하고 재호출 시에는 max를 사용한다.

4. 영역의 넓이는 탐색이 끝날 때 마다 ArrayList에 저장하고, 오름차순으로 출력하라고 했으니 Collections.sort(list)를 사용한다.

5. 분리된 영역의 수는 list.size()를 사용하면 된다.

 

 

<코드 구현>

import java.util.*;

/*
[백준] 2583번 - 영역 구하기 (Java)
*/

public class Main {
    static int M, N, K;
    static int A[][];    
    static boolean visited[][];

    void InputData() {
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        K = in.nextInt();
        A = new int[M][N];
        
        for (int i=0; i<K; i++) {
            int y1 = in.nextInt();
            int x1 = in.nextInt();
            int y2 = in.nextInt();
            int x2 = in.nextInt();
            for (int x=x1; x<x2; x++) {
                for (int y=y1; y<y2; y++) {
                    A[x][y] = 1;//좌표의 범위만큼 사각형을 1로 채운다
                }
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void DFS(int x, int y, int count) {
        visited[x][y] = true;
        max = Math.max(max, count);
        //System.out.println("DFS("+x+", "+y+", "+count+")");
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if (A[nx][ny] == 1) continue;
            if (visited[nx][ny]) continue;
            DFS(nx, ny, max+1);//다시 돌아갔을 때 stack에는 이전 count값이 사용되므로 최신 max를 count 대신 사용한다.
        }
    }

    int max = 0;
    void Solve() {
        ArrayList<Integer> list = new ArrayList<>();
        visited = new boolean[M][N];
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                if (visited[i][j]) continue;
                if (A[i][j] == 1) continue;
                DFS(i, j, 1);
                list.add(max);
                max = 0;
            }
        }

        System.out.println(list.size());
        Collections.sort(list);        
        for (int x : list)
            System.out.print(x+" ");
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출 결과>