2583번 : 영역 구하기 [Java]

 

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

2583번: 영역 구하기

 

해결 방안

먼저 좌표를 받아 이차원배열에 직사각형을 -1로 채운다. 

그 후 배열을 돌면서 -1이 아닌 수를 만날 경우 분리된 영역 수를 체크하기 위한 변수를 증가시키고 너비 우선 탐색을 실시한다. 너비 우선 탐색을 하면서 직사각형 내부가 아닌 부분을 발견하면 -1로 바꾸어주고 각 영역의 넓이 체크를 위한 변수를 증가시킨다.

 

주의할 점

처음 좌표를 받을 때 맵에 들어갈 곳을 잘 생각해서 채워 넣자,,

 

아쉬운 점

출력을 위한 코드가 지저분한 느낌이라 더 간단한 방법을 고민해보자,,

 

전체 코드

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

public class Main {
	static int M, N, K;
	static int[][] map;
	static int cnt;
	static int space;
	static ArrayList<Integer> ans;

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

		for (int k = 0; k < K; k++) {
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			makemap(x1, y1, x2, y2);
		}
		ans = new ArrayList();

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] != -1) {
					cnt = 0;
					search(i, j);
				}
			}
		}

		Collections.sort(ans);
		System.out.println(space);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < ans.size(); i++)
			sb.append(ans.get(i) + " ");
		System.out.println(sb);
	}

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	private static void search(int i, int j) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { i, j });
		map[i][j] = -1;
		cnt++;

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				if (isIn(nr, nc) && map[nr][nc] != -1) {
					q.add(new int[] { nr, nc });
					map[nr][nc] = -1;
					cnt++;
				}
			}
		}
		ans.add(cnt);
		space++;
	}

	private static boolean isIn(int nr, int nc) {
		if (nr < 0 || nc < 0 || nr >= M || nc >= N)
			return false;
		else
			return true;
	}

	private static void makemap(int x1, int y1, int x2, int y2) {
		for (int y = x1; y < x2; y++) {
			for (int x = y1; x < y2; x++) {
				map[x][y] = -1;
			}
		}

	}
}