영역구하기 (정올 1457, 백준 2583)

문제링크

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=99&sfl=wr_subject&stx=%EC%98%81%EC%97%AD 

JUNGOL

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

2583번: 영역 구하기

풀이

단순 BFS 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	/*
	 * bfs
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		boolean[][] map=new boolean[n][m];
		for(int l=0;l<k;l++) {
			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());
			for(int i=y1;i<y2;i++) {
				for(int j=x1;j<x2;j++) {
					map[i][j]=true;
				}
			}
		}
		int cnt=0;
		PriorityQueue<Integer> pq=new PriorityQueue<>();
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(map[i][j])continue;
				Queue<Integer> q=new LinkedList<>();
				q.add(i*100+j);
				cnt++;
				int area=0;
				while(!q.isEmpty()) {
					int temp=q.poll();
					if(map[temp/100][temp%100])continue;
					map[temp/100][temp%100]=true;
					area++;
					if(temp/100+1<n&&!map[temp/100+1][temp%100])q.add(temp+100);
					if(temp/100-1>=0&&!map[temp/100-1][temp%100])q.add(temp-100);
					if(temp%100+1<m&&!map[temp/100][temp%100+1])q.add(temp+1);
					if(temp%100-1>=0&&!map[temp/100][temp%100-1])q.add(temp-1);
				}
				pq.add(area);
			}
		}
		System.out.println(cnt);
		while(!pq.isEmpty())System.out.printf(pq.poll()+" ");
	}
}