백준 2583_영역 구하기(JAVA)

 

www.acmicpc.net/problem/2583

2583번: 영역 구하기

[문제 풀이]

너비 우선 탐색을 이용하여 문제를 풀었습니다.

 

이 문제는 사각형의 좌표가 주어 졌을 때 사각형 공간을 제외한 나머지 공간이 몇개로 나누어질 수 있는지에 대해 찾는 문제였습니다. 문제를 풀기 위해 2차원 배열에 사각형이 차지하고 있는 부분을 먼저 적은 후 2차원 배열을 순회하면서 체크 되지 않은 부분이 있다면 BFS를 통해 영역을 구해 주었습니다.

 

코드 설명

• 입력으로 주어진 값을 받아 변수와 배열에 저장해 줍니다.
• 사각형의 꼭지점을 이용하여 2차원 배열에 사각형의 공간을 체크해 줍니다.
• 사각형 공간 체크가 끝났다면 2차원 배열을 순회하면서 체크가 안된 부분이 있다면 BFS로 체크하고 크기를 반환합니다.
• 이 문제의 경우 M, N이 90도 뒤집혀져 있기 때문에 그 점에 유의하여 풀어야 합니다.

[코드]

package coding;

import java.awt.*;
import java.io.*;
import java.util.*;

class Main{
	
	static int M, N, K;
	static int[][] map = new int[100][100];
	static int[][] rec = new int[100][4];
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0 ,-1, 0};
	
	public static int BFS(int r, int c) {
		
		int answer = 1;
		
		map[r][c] = 1;
		
		Queue<Point> queue = new LinkedList<>();
		
		queue.add(new Point(r, c));
		
		while(!queue.isEmpty()) {
			Point point = queue.poll();
			int x = point.x;
			int y = point.y;
			
			for(int i = 0; i < 4; i ++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 1)
					continue;
				
				answer++;
				map[nx][ny] = 1;
				queue.add(new Point(nx, ny));
			}
		}
			
		return answer;
		
	}
	
	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());
		
		//꼭지점 입력
		for(int i = 0; i < K; i++) {
			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());
			
			rec[i][0] = x1;
			rec[i][1] = y1;
			rec[i][2] = x2;
			rec[i][3] = y2;
		}
		
		//BFS 체크
		for(int i = 0; i < K; i++) {
			for(int x = rec[i][0]; x < rec[i][2]; x++) {
				for(int y = rec[i][1]; y < rec[i][3]; y++) {
					map[x][y] = 1;
				}
			}
		}
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					list.add(BFS(i, j));
				}
			}
		}
		
		list.sort(null);
		
		System.out.println(list.size());
		for(int a : list)
			System.out.print(a + " ");
		
	}
}