백준 2583번 : 영역 구하기(Java)

 

2583번: 영역 구하기

---

[풀이]

 

- DFS를 이용하여 문제를 풀었습니다.(DFS관련 유형에서 기본문제입니다.)
- visited를 이용해서 재귀를 해야하는지, 안해야하는지 구분을 하려했습니다.
  - 하지만, 이 부분에 대해서는 arr 변수에 값을 1로 재할당하는 부분이 있어서 없어도 되는 부분입니다.
- 영역의 개수는 리스트의 사이즈와 동일합니다.
- 각 영역의 넓이를 출력해야 하므로 리스트에 담아 정렬 후, 출력합니다.

---

[코드]

 

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

public class Main {

	static int m, n, k, count;
	static int[][] arr;
	static boolean[][] visited;
	static List<Integer> list = new ArrayList<>();
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};

	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];

		while (k-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

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

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][j] == 0) {
					count = 0;
					solve(i, j);
					list.add(count);
				}
			}
		}

		Collections.sort(list);
		System.out.println(list.size());
		for (Integer number : list) {
			System.out.print(number + " ");
		}
	}

	public static void solve(int x, int y) {
		count += 1;
		visited[x][y] = true;
		arr[x][y] = 1;
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX >= 0 && nextY >= 0 && nextX < m && nextY < n) {
				if (!visited[nextX][nextY] && arr[nextX][nextY] == 0) {
					solve(nextX, nextY);
				}
			}
		}
	}
}