[Baekjoon Online Judge] 2583번: 영역 구하기

2583번: 영역 구하기

요구사항

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

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

입력

 - 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

 - 첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

---

 

문제에 나온 그림은 x, y를 좌표로 표현했기 때문에 x가 가로, y가 세로로 표현되어 있다. 이것을 Java 이차배열로 구현하기 위해서는 int[][]로 생성해야 하는데, 배열의 크기를 int[n][m]으로 설정해야 한다.

 

이제 입력 받은 좌표에 해당하는 이차배열을 1로 채워둔다.

 

m = Integer.parseInt(input[0]);
n = Integer.parseInt(input[1]);
int k = Integer.parseInt(input[2]);

map = new int[n][m];
visited = new boolean[n][m];

for (int i = 0; i < k; i++) {
    String[] inputLocation = bufferedReader.readLine().split(" ");     
    int x1 = Integer.parseInt(inputLocation[0]);
    int y1 = Integer.parseInt(inputLocation[1]);

    int x2 = Integer.parseInt(inputLocation[2]);
    int y2 = Integer.parseInt(inputLocation[3]);

    for (int x = x1; x < x2; x++) {
        for (int y = y1; y < y2; y++) {
            map[x][y] = 1;
        }
    }
}

 

이제 BFS 혹은 DFS를 활용하여 map에 0인 부분을 탐색하며 해당 크기의 넓이를 반환하는 메소드로 생성한다.

 

우선 BFS를 활용한 방식의 코드이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Baekjoon2583 {

    static int[][] map;
    static boolean[][] visited;
    static int[] xMove = {-1, 1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};
    static int m, n;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static int bfs(int startX, int startY) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(startX, startY));
        visited[startX][startY] = true;
        int count = 1;

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            int pollX = location.x;
            int pollY = location.y;

            for (int i = 0; i < 4; i++) {
                int x = pollX + xMove[i];
                int y = pollY + yMove[i];

                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    visited[x][y] = true;
                    ++count;
                }
            }
        }
        return count;
    }

    private static boolean isLocation(int x, int y) {
        if (x >= 0 && y >= 0 && x < n && y < m && map[x][y] == 0 && !visited[x][y]) return true;
        return false;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");

        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);
        int k = Integer.parseInt(input[2]);

        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < k; i++) {
            String[] inputLocation = bufferedReader.readLine().split(" ");
            int x1 = Integer.parseInt(inputLocation[0]);
            int y1 = Integer.parseInt(inputLocation[1]);

            int x2 = Integer.parseInt(inputLocation[2]);
            int y2 = Integer.parseInt(inputLocation[3]);

            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    map[x][y] = 1;
                }
            }
        }

        List<Integer> resultList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0 && !visited[i][j])
                    resultList.add(bfs(i, j));
            }
        }

        Collections.sort(resultList);

        bufferedWriter.write(resultList.size() + "\n");
        for (Integer result : resultList)
            bufferedWriter.write(result + " ");

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

각각의 넓이를 탐색하고 count를 반환한다. 해당 count는 resultList에 저장되어 정렬한 후 출력하여 해결하였다.

 

밑의 코드는 DFS로 풀이한 방식이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Baekjoon2583 {

    static int[][] map;
    static boolean[][] visited;
    static int[] xMove = {-1, 1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};
    static int m, n;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static int dfs(int startX, int startY, int count) {
        visited[startX][startY] = true;

        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int x = startX + xMove[i];
                int y = startY + yMove[i];

                if (isLocation(x, y)) {
                    count = Math.max(count, dfs(x, y, ++count));
                }
            }
        }

        return count;
    }

    private static boolean isLocation(int x, int y) {
        if (x >= 0 && y >= 0 && x < n && y < m && map[x][y] == 0 && !visited[x][y]) return true;
        return false;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");

        m = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);
        int k = Integer.parseInt(input[2]);

        map = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < k; i++) {
            String[] inputLocation = bufferedReader.readLine().split(" ");
            int x1 = Integer.parseInt(inputLocation[0]);
            int y1 = Integer.parseInt(inputLocation[1]);

            int x2 = Integer.parseInt(inputLocation[2]);
            int y2 = Integer.parseInt(inputLocation[3]);

            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    map[x][y] = 1;
                }
            }
        }

        List<Integer> resultList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0 && !visited[i][j])
                    resultList.add(dfs(i, j, 1));
            }
        }

        Collections.sort(resultList);

        bufferedWriter.write(resultList.size() + "\n");
        for (Integer result : resultList)
            bufferedWriter.write(result + " ");

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

count를 구하는 DFS를 제외하고 나머지 부분은 위의 코드와 유사하다.