백준 자바 문제풀이 #2583

영역 구하기

이제 기본적인 백트래킹 문제는 문제파악도 없이 거의 기계적으로 풀어내고 있다.

이번 문제는 실버1 이지만 기본적인 DFS에서 크게 벗어나지 않았다.

좌표를 입력받아 이차원 배열로 나타내고

DFS를 이용해 상하좌우를 체크해주면 된다.

package Silver.S1;

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 S2583 {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int m, n, count, group;
    static boolean[][] board, visited;
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) 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());
        int[][] site = new int[k][4];
        board = new boolean[m][n];
        visited = new boolean[m][n];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                site[i][j] = Integer.parseInt(st.nextToken());
            }

            int x = site[i][0];
            int y = site[i][1];
            int a = site[i][2];
            int b = site[i][3];

            for (int j = y; j < b; j++) {
                for (int l = x; l < a; l++) {
                    board[j][l] = true;
                }
            }

        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!board[i][j] && !visited[i][j]) {
                    count = 0;
                    DFS(i, j);
                    list.add(count);
                    group++;
                }
            }
        }

        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        sb.append(group).append("\n");
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i)).append(" ");
        }
        System.out.println(sb);
    }

    static void DFS(int row, int col){
        visited[row][col] = true;
        count++;
        for (int i = 0; i < 4; i++) {
            if (row + dy[i] < 0 || row + dy[i] > m - 1 || col + dx[i] < 0 || col + dx[i] > n - 1) {
                continue;
            }

            if (!board[row + dy[i]][col + dx[i]] && !visited[row + dy[i]][col + dx[i]]) {
                DFS(row + dy[i], col + dx[i]);
            }
        }
    }
}