[BOJ] 1941: 영역 구하기 (Java)

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

2583번: 영역 구하기

걸린 시간 : 47분 8초 (자바 미숙)

---

자바로 코테가 미숙해서 열심히 푸는 중...!! 자바 언어에 익숙해지고자 풀어봤다.

문제에서 입력할 때 M, N 순서로 주기도 하고 N, M 순서로 주기도 해서 주의해야 한다.

알고리즘

영역이 100 X 100 이하이므로 이 크기의 2차원 배열을 만들어 입력 받을 때 칠해진 곳을 체크한다.

그 후 DFS로 방문체크를 하며 연결요소의 수를 세면 된다. BFS도 가능하지만, 재귀가 가능한 DFS가 구현이 더 쉽다.

정답 코드

import java.io.*;
import java.util.*;

public class BOJ2583 {
    static boolean[][] board = new boolean[101][101];
    static boolean[][] vis = new boolean[101][101];
    static int[] di = {-1, 0, 0, 1};
    static int[] dj = {0, -1, 1, 0};
    static int M, N, K;
    static List<Integer> area = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        String[] tmp = s.split(" ");
        M = Integer.parseInt(tmp[0]);
        N = Integer.parseInt(tmp[1]);
        K = Integer.parseInt(tmp[2]);
        while (K-- > 0) {
            s = bf.readLine();
            StringTokenizer st = new StringTokenizer(s);
            int j1 = Integer.parseInt(st.nextToken());
            int i1 = Integer.parseInt(st.nextToken());
            int j2 = Integer.parseInt(st.nextToken());
            int i2 = Integer.parseInt(st.nextToken());
            for (int i = i1; i < i2; i++) {
                for (int j = j1; j < j2; j++) {
                    board[i][j] = true;
                }
            }
        }
        int answer = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!vis[i][j] && !board[i][j]) {
                    answer++;
                    area.add(dfs(i ,j));
                }
            }
        }
        System.out.println(answer);
        Collections.sort(area);
        for (int a : area) {
            System.out.print(a + " ");
        }
    }

    static int dfs (int ci, int cj) {
        vis[ci][cj] = true;
        int ret = 1;
        for (int k = 0; k < 4; k++) {
            int ni = ci + di[k];
            int nj = cj + dj[k];
            if (ni < 0 || ni >= M || nj < 0 || nj >= N || vis[ni][nj] || board[ni][nj]) continue;
            ret += dfs(ni, nj);
        }
        return ret;
    }
}