백준 2583 영역 구하기

 

문제 접근

- 사각형으로 칠해진 부분 외에 영역이 몇개의 영역인지, 그리고 영역의 크기가 각각 얼마나 되는지를 구하는 문제이다.

- 다른 문제들에서는 친절하게 좌표값이 주어지지만 해당 문제는 꼭지점의 위치를 주기 때문에, 영역을 구하는 과정이 까다로웠다.

(둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다.)

그래서 아래와 같이 (c1,r1) ~ (c2,r2)를 구하고, 해당 영역을 모두 1로 채워주는 작업을 진행하였다. 

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());

    int r1 = M - y2;
    int r2 = M - y1 - 1;
    int c1 = x1;
    int c2 = x2 - 1;
    //  (1.0) ~ (2,3)
    //  (0.1) ~ (3,1)
    //  (3,4) ~ (4,5)
    for (int r = r1; r <= r2; r++) {
        for (int c = c1; c <= c2; c++) {
            maze[r][c] = 1;
        }
    }
}

 

헷갈렸던 점

- max 값을 static으로 주지 않고 dfs(x,y cnt)에서 가장 큰 cnt 값을 max 값으로 대입해주었더니 max 값이 잘못 나오는 현상이 있었다. 이것 때문에 한참 삽질했다. 

- 이유를 찾아보니 이동할 경로가 없을 때에 소멸되기 때문이었다. 그래서 max 값을 static으로 주고 cnt를 없애버려서 처리했다. 

 

반례

5 7 3
0 2 4 4
1 1 2 5
2 2 4 4

 

2

1 24

 

소스 코드

package Baekjoon;

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

public class BOK_2583 {
    public static void main(String[] args) throws IOException {
        solution();
    }
    static int[][] maze;
    static boolean[][] visited;
    static int M;
    static int N;
    static int max;
    static void solution() 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());
        int K = Integer.parseInt(st.nextToken());
        maze = new int[M][N];
        visited = new boolean[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());

            int r1 = M - y2; 
            int r2 = M - y1 - 1;
            int c1 = x1; 
            int c2 = x2 - 1; 
            //  (1.0) ~ (2,3)
            //  (0.1) ~ (3,1)
            //  (3,4) ~ (4,5)
            for (int r = r1; r <= r2; r++) {
                for (int c = c1; c <= c2; c++) {
                    maze[r][c] = 1;
                }
            }
        }

        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 각 DFS마다의 넓이를 구하기 위해서 미리 필터링을 해준다.
                if(!visited[i][j] && maze[i][j] != 1){
                    max = 0;
                    dfs(i, j);
                    array.add(max);
                }
            }
        }
        Collections.sort(array);
        System.out.println(array.size());
        for(int i=0; i<array.size(); i++){
            if(i == array.size()-1)
                System.out.print(array.get(i));
            else
                System.out.print(array.get(i)+" ");
        }
    }

    static void dfs(int x, int y){
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        visited[x][y] = true;
        max += 1;

        for(int i=0; i<4; i++){
            int nx = dx[i] + x;
            int ny = dy[i] + y;

            if(nx>=0 && ny>=0 && nx<M && ny <N) {
                if(!visited[nx][ny] && maze[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    dfs(nx, ny);
                }
            }
        }

    }
}