[JAVA] 백준 알고리즘 2583 : 영역 구하기

영역 구하기

문제

소스

import java.util.Collections;
import java.util.Iterator;
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 visit[][];
	static Queue<Integer> qx = new LinkedList<Integer>();
	static Queue<Integer> qy = new LinkedList<Integer>();
	static LinkedList<Integer> re = new LinkedList<Integer>();
	
	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];
		visit = new int[M][N];

		for (int i=0; i<K*2; i++) {
			qx.add(sc.nextInt());
			qy.add(sc.nextInt());
		}
		
		int sx, sy; // 시작 좌표
		int ex, ey; // 종료 좌표
		
		while(!qx.isEmpty() && !qy.isEmpty()) {
			sx = qx.poll();
			sy = qy.poll();
			ex = qx.poll();
			ey = qy.poll();

			for(int i=sy; i<ey; i++) {
				for(int j=sx; j<ex; j++) {
					map[i][j] = 1; // 직사각형이 포함된 영역 표시
				}
			}			
		}
		
		check();
	}
	
	public static void check() {

		int x, y, tx, ty, cnt;
		
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] == 0 && visit[i][j] == 0) { // 빈공간이면서 아직 방문하지 않았다면
					cnt=1;
					visit[i][j] = 1; // 방문 표시
					qx.add(i);
					qy.add(j);
					
					while(!qx.isEmpty() && !qy.isEmpty()) {
						x = qx.poll();
						y = qy.poll();
						
						// 우
						tx=x; ty=y+1;
						if(ty<N && map[tx][ty] == 0 && visit[tx][ty] == 0) {
							qx.add(tx);
							qy.add(ty);
							visit[tx][ty] = 1;
							cnt++;
						}
						
						// 좌
						tx=x; ty=y-1;
						if(ty>=0 && map[tx][ty] == 0 && visit[tx][ty] == 0) {
							qx.add(tx);
							qy.add(ty);
							visit[tx][ty] = 1;
							cnt++;
						}
						
						// 상
						tx=x-1; ty=y;
						if(tx>=0 && map[tx][ty] == 0 && visit[tx][ty] == 0) {
							qx.add(tx);
							qy.add(ty);
							visit[tx][ty] = 1;
							cnt++;
						}
						
						// 하
						tx=x+1; ty=y;
						if(tx<M && map[tx][ty] == 0 && visit[tx][ty] == 0) {
							qx.add(tx);
							qy.add(ty);
							visit[tx][ty] = 1;
							cnt++;
						}
						
					}
					re.add(cnt);				
				}
			}
		}
		
		Collections.sort(re); // 오름차순 정렬
		System.out.println(re.size()); // 영역의 개수
		Iterator itr = re.iterator();
		while(itr.hasNext()) {
			System.out.print(itr.next() + " "); // 각 영역의 넓이
		}
	}
}

출처

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