[Java] 백준 2583번: 영역 구하기

문제

💡 일단 생각하기!

BFS 사용해서 직사각형의 영역이 아닌 부분, 즉 영역의 개수를 세고 넓이를 구해주면 된다. 영역의 넓이는 Queue에 넣을때마다 ++해준 뒤 ArrayList에 넣는다. 영역의 넓이를 오름차순으로 출력해줘야 하기 때문에 Collections.sort(list) 해주면 된다.
BFS를 돌리던 중 dx, dy를 잘못 설정해서 1시간을 헤맸다 ㅋㅋ.. 풀이 방법을 아는 문제라고 생각해서 풀다가 꼼꼼히 보지 못한 탓이다. 문제가 풀리지 않을땐 디버깅 하기, 코드 잘 확인하기, 범위 확인하기!

풀이

package 알고리즘;

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

/**
 * 백준 2583번 영역 구하기
 * 메모리 : 12524KB 시간 : 76ms
 * 
 * 아이디어
 * - 직사각형의 좌표를 받으면 바로 배열에 표시해주고 표시가 안된 영역의 개수와 넓이를 구한다
 * - BFS를 사용하여 영역의 개수와 넓이를 구해주는데 넓이는 Queue에 넣을때마다 ++
 * - 넓이를 ArrayList에 넣고 Collections.sort(list)하면 오름차순으로 정렬됨
 * - 출력 부분 확인 잘하기, 변수 확인 잘하기..
 */
public class BJ_2583_영역구하기_김유나 {
	static class Point {
		int x, y;
		
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static boolean isVisited[][];
	static int arr[][], area[], count = 0, M, N, deltas[][] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
	static ArrayList<Integer> list = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		int num = Integer.parseInt(st.nextToken());
		
		arr = new int[M][N];
		isVisited = new boolean[M][N];
		area = new int[100];
		
		for (int i = 0; i < num; i++) {
			st = new StringTokenizer(br.readLine());
			
			int lx = Integer.parseInt(st.nextToken());
			int ly = Integer.parseInt(st.nextToken());
			int rx = Integer.parseInt(st.nextToken());
			int ry = Integer.parseInt(st.nextToken());
			
			
			for (int k = lx; k < rx; k++) {
				for (int j = ly; j < ry; j++) {
					arr[j][k] = 1;
				}
			}
		}
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (arr[i][j] == 0 && !isVisited[i][j]) {
					list.add(bfs(i, j));
					count++;
				}
			}
		}
		
		Collections.sort(list);
		
		sb.append(count + "\n");
		for (int i = 0 ; i < list.size(); i++) {
			sb.append(list.get(i) + " ");
		}
		
		System.out.println(sb);
	}
	
	
	static int bfs(int x, int y) {
		Queue<Point> q = new ArrayDeque<>();
		q.add(new Point(x, y));
		isVisited[x][y] = true;
		int cnt = 1;
	
		while (!q.isEmpty()) {
			Point cur = q.poll();
			int X = cur.x;
			int Y = cur.y;
			
			for (int i = 0; i < 4; i++) {
				int dx = X + deltas[i][0];
				int dy = Y + deltas[i][1];
				
				if (dx >= 0 && dy >= 0 && dx < M && dy < N) {
					if (!isVisited[dx][dy] && arr[dx][dy] == 0) {
						q.add(new Point(dx, dy));
						isVisited[dx][dy] = true;
						cnt++;
					}
				}
			}
		}
		
		return cnt;
	}
}