[백준] 2583번 영역 구하기

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

2583번: 영역 구하기

문제 : 분리된 영역에서 각 영역의 넓이가 얼마인지 구하기 문제 풀이 :  dfs활용 꼭지점의 좌표(0,0)을 왼쪽 위로 하고 , 오른쪽 아래 꼭지점의 좌표를 (M,N)으로 입력받아서 풀었습니다. count 변수는 영역의 넓이를 구해주고, answer 변수는 영역의 개수를 구해줍니다.

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

public class Main {
	static int[][] map, dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static boolean[][] visited;
	static int M, N, K;
	static int count = 0, answer = 0;
	static ArrayList list = new ArrayList();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		K = sc.nextInt();
		map = new int[M][N];
		visited = new boolean[M][N];

		for (int i = 0; i < K; i++) {
			int y1 = sc.nextInt();
			int x1 = sc.nextInt();
			int y2 = sc.nextInt();
			int x2 = sc.nextInt();

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

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0 && !visited[i][j]) {
					count = 0;
					dfs(i, j);
					answer++;
					list.add(count);

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

	}// eom

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

		for (int i = 0; i < 4; i++) {
			int nx = dir[i][0] + x;
			int ny = dir[i][1] + y;
			if (isInside(nx, ny) && map[nx][ny] == 0 && !visited[nx][ny]) {
				dfs(nx, ny);
			}
		}

	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < M && y >= 0 && y < N;
	}

}