[BJ2583] 영역 구하기

 백준 - 영역 구하기 

문제 링크

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

2583번: 영역 구하기

 

문제 입출력

4 4 1
0 0 3 3

1
7

100 100 1
0 0 1 1

1
9999

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
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 cnt1, cnt2, M, N, K;
	static int[][] rect, map;

	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static List<Integer> list = new ArrayList<>();


	public static void main(String[] args) throws Exception {
		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());

		map = new int[M][N];
		rect = new int[K][4];
		list.clear();
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) rect[i][j] = Integer.parseInt(st.nextToken());
		}

		// 직사각형 칠하기
		for (int i = 0; i < K; i++) {
			int sx = rect[i][0];
			int sy = (M - 1) - rect[i][1];
			int ex = rect[i][2] - 1;
			int ey = M - rect[i][3];

			for (int y = ey; y <= sy; y++) for (int x = sx; x <= ex; x++) map[y][x] = 1;
		}

		// 탐색
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				cnt2 = 0;
				if (map[i][j] == 0) {
					dfs(i, j);
					cnt1++;
					list.add(cnt2);
				}

			}

		}

		System.out.println(cnt1);
		Collections.sort(list);
		for (int x : list) System.out.print(x + " ");

	} // end main


	private static void dfs(int y, int x) {
		map[y][x] = 1;
		cnt2++;

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

			if (ny < 0 || ny >= M || nx < 0 || nx >= N) continue;
			if (map[ny][nx] == 1) continue;

			dfs(ny, nx);
		}

		return;

	} // end dfs
}

• dfs 를 이용하여 풀 수 있습니다.
• 기존에 사용하는 배열의 인덱스가 아닌 좌표의 인덱스를 따르고 있습니다.
• dfs 를 구하는 것보다 해당 로직을 짜는 데에 더 시간을 투자했네요.
• 몇 칸이 떨어졌는지를 세서 기존의 배열의 인덱스 같이 변경을 해주고 직사각형이라는 뜻으로 1로 표시했습니다.

 

 

 

 

 

 

 

 

 

# 백준 영역 구하기 반례 # 백준 영역구하기 반례 # 백준 영역 구하기 java # 백준 영역 구하기 dfs

---