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

영역 구하기

문제

---

문제 설명

모눈종이와 안에 들어갈 사각형들의 왼쪽 아래와 오른쪽 위 꼭짓점의 x, y 좌표값이 주어졌을 때 사각형이 아닌 영역들의 개수와 넓이를 구하는 문제이다.

최소거리를 구하는 것이 아니기 때문에 DFS를 사용해서 완전 탐색을 해서 풀어야한다.

문제에서의 x,y 좌표는 왼쪽 아래에서부터 세기 때문에 입력받을 때의 y좌표는 높이에서 빼줘야 하고 그 이후에 해당하는 사각형들을 배열에 넣어주면 된다.

for (int K = 0; K < k; K++) {
	st = new StringTokenizer(br.readLine());
	int x1 = Integer.parseInt(st.nextToken());
	int y1 = m - Integer.parseInt(st.nextToken());
	int x2 = Integer.parseInt(st.nextToken());
	int y2 = m - Integer.parseInt(st.nextToken());

	int startX = Math.min(x1, x2);
	int endX = Math.max(x1, x2);
	int startY = Math.min(y1, y2);
	int endY = Math.max(y1, y2);

	for (int y = startY; y < endY; y++) {
		for (int x = startX; x < endX; x++) {
			arr[y][x] = 1;
		}
	}
}

그리고 이제 우리가 구해야할 영역들의 넓이를 저장해줄 result 배열의 크기는 영역이 몇개나 나올지 모르기 때문에 ArrayList로 선언하고 visited 배열을 통해 만약에 방문하지 않았고 배열의 값이 0이면 count변수를 1로 초기화 한후 dfs를 돌고 다 돌았다면 해당 count 변수를 ArrayList에 넣어주는 방식으로 진행하였다.

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

그리고 DFS 로직은 다른 문제와 크게 다르지 않게 아래와 같이 구현하였다.

public static void dfs(int y, int x) {
	visited[y][x] = true;

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

		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
			continue;
		}
		if (!visited[ny][nx] && arr[ny][nx] == 0) {
			count++;
			dfs(ny, nx);
        }
    }
}

이렇게 세가지 주요 로직들을 갖고 완성된 코드는 아래와 같다.

---

코드

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

public class Main_2583 {
    static int m, n, k;
    static int[][] arr;
    static boolean[][] visited;
    static int count;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static ArrayList<Integer> result = 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());
        k = Integer.parseInt(st.nextToken());

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

        for (int K = 0; K < k; K++) {
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = m - Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = m - Integer.parseInt(st.nextToken());

            int startX = Math.min(x1, x2);
            int endX = Math.max(x1, x2);
            int startY = Math.min(y1, y2);
            int endY = Math.max(y1, y2);

            for (int y = startY; y < endY; y++) {
                for (int x = startX; x < endX; x++) {
                    arr[y][x] = 1;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(!visited[i][j] && arr[i][j] == 0) {
                    count = 1;
                    dfs(i, j);
                    result.add(count);
                }
            }
        }
        System.out.println(result.size());

        Collections.sort(result);

        for (Integer i : result) {
            System.out.print(i + " ");
        }
    }

    public static void dfs(int y, int x) {
        visited[y][x] = true;

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

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            if (!visited[ny][nx] && arr[ny][nx] == 0) {
                count++;
                dfs(ny, nx);
            }
        }
    }
}