[ 백준 ] [ 2583 ] [ 자바 ] 영역구하기

간단한 문제 

영역을 구하는 건 간단하다 . 약간 문제에서 헷갈릴수 있는게

평소 알던 좌표 위치랑 정반대에 있다

처음에는 좌표 컨버팅 모듈을 만들어야하나했는데

그냥 좌표는 평상시 배열좌표를 써도 무방하다고 판단된다. 어처피 뒤집으면 똑같으니 ㅎ

직사각형을 배열에다가 입력한다음에

bfs로 문제를 해결해나가면 된다. 

한방에 클리어는 정말 오래간만인거같다..

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

class paperPoint {
	int y; int x;
	paperPoint(int y, int x){
		this.y = y;
		this.x = x; 
	}
}
public class Main_backjoon_2583_영역구하기 {
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int[][] MAP = new int[101][101];
	static boolean[][] visited = new boolean[101][101];
	static int M;
	static int N;
	static int K;
	static int divide = 0;
	static LinkedList arr; 
	static LinkedList countList = new LinkedList();
	static Queue q = new LinkedList();
	public static void main(String[] args) throws IOException {
		
		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(), " ");
			arr = new LinkedList();
			while(st.hasMoreTokens()) {
				arr.add(Integer.parseInt( st.nextToken() ));
			}
			makeMap(arr);
			//printMap();
		}
		for(int i = 0 ; i < M; i++) {
			for(int j = 0; j < N; j++) {
				if ( MAP[i][j] == 0 && visited[i][j] == false) {
					getPaper(i, j);
					divide++;
				}
			}
		}
		System.out.println(divide);
		
		Collections.sort(countList);
		for(int i = 0; i < countList.size(); i++ ) {
			System.out.print(countList.get(i) + " ");
		}

		
	}

	public static void getPaper(int y, int x) {
		q.add(new paperPoint(y, x));
		visited[y][x] = true;
		int count = 0 ;
		while(!q.isEmpty()){
			paperPoint p = q.poll();
			count += 1;
			for(int i = 0; i < 4; i++) {
				int yy = p.y + dy[i];
				int xx = p.x + dx[i];
				if( yy >= 0 && yy < M && xx >=0 && xx < N) {
					if( MAP[yy][xx] == 0 && visited[yy][xx] == false ) {
						q.add(new paperPoint(yy,xx));
						visited[yy][xx] = true;
						
					}
				}
			}
		}
		countList.add(count);
	}
	public static void makeMap(LinkedList arr) {
		int y =  arr.get(0);
		int x =  arr.get(1);
		int yy = arr.get(2);
		int xx = arr.get(3);
		
		for(int i = x ; i < xx; i++) {
			for(int j = y; j < yy; j++) {
				MAP[i][j] = 1;
			}
		}
	}
	public static void printMap() {
		for(int i = 0 ; i < M; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print( MAP[i][j] + " " );
			}
			System.out.println();
		}
		System.out.println();
	}
}