[Java] 백준 2583 : 영역 구하기

문제 링크

1.

입력 데이터를 어떻게 처리할지에 대한 고민을 조금 했던 문제이다.

 

데이터 배열을 만들고 난 후에는 단지번호붙이기 문제와 유사해 쉽게 풀 수 있다.

 

 

2.

직사각형의 왼쪽 아래 꼭짓점의 $(x, y)$과 오른쪽 위 꼭짓점의 $(x, y)$가 주어진다.

일단 노트에다가 이를 고려해 찍어보았다.

 

문제는 이 좌표계를 배열화 시켜야 하는 것인데, 고민해보면 다음과 같은 규칙을 찾을 수 있다.

 

$(2, 0)$ ~ $(4, 4)$ 이라면, data[0][2] ~ data[3][3]

$(1, 1)$ ~ $(2, 5)$ 이라면, data[1][1] ~ data[4][1]

$(4, 0)$ ~ $(6, 2)$ 이라면, data[4][0] ~ data[1][5]

 

배열 모양은 좌표계를 x축을 기준으로 대칭시킨 모양이 된다.

 

 

다음 BFS 메커니즘은 다음과 같다.

1. data[i][j] 가 0 이거나 방문하지 않았을 때 bfs()를 수행한다.

2. bfs를 수행할 때 비어있는 곳의 개수를 구하기 위해 cnt를 + 1 한다.

3. bfs가 끝나는 시점에 list에 추가한다. (0이라면 + 1을 해줘야 함)

4. list를 오름차순 정렬하고 출력한다.

 

3.

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int m, n, k;
    static int[][] data;
    static ArrayList<Integer> answer = new ArrayList<>();
    static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();
        k = sc.nextInt();

        data = new int[m][n];
        for (int t = 0; t < k; t++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            for (int i = y1; i < y2; i++) {
                for (int j = x1; j < x2; j++) {
                    data[i][j] = 1;
                }
            }
        }

        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (data[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j);
                }
            }
        }

        Collections.sort(answer);
        System.out.println(answer.size());
        for (int i = 0; i < answer.size(); i++) {
            System.out.print(answer.get(i) + " ");
        }
        sc.close();
    }

    static void bfs(int a, int b) {
        Queue<Pos> q = new LinkedList<>();
        int[] dx = { 1, -1, 0, 0 };
        int[] dy = { 0, 0, 1, -1 };
        int cnt = 0;

        q.offer(new Pos(a, b));
        while (!q.isEmpty()) {
            Pos temp = q.poll();

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

                if (0 <= nx && nx < m && 0 <= ny && ny < n) {
                    if (data[nx][ny] == 0 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.offer(new Pos(nx, ny));
                        cnt++;
                    }
                }
            }
        }

        if (cnt == 0) {
            answer.add(cnt + 1);
        } else {
            answer.add(cnt);
        }
    }
}

class Pos {
    int x, y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

 

4.

오랜만에 혼자 힘으로 풀었네..