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

www.acmicpc.net/problem/2583

2583번: 영역 구하기

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

public class Main {
	static int M, N, K;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static List<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());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			for(int j=a; j<c; j++) {
				for(int k=b; k<d; k++) {
					map[j][k] = 1;
				}
			}
		}
		
		int result = 0;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(!visited[i][j] && map[i][j] ==0) {
					bfs(i,j);
					result++;
				}
			}
		}
		
		System.out.println(result);
		Collections.sort(list);
		for(int i=0; i<list.size(); i++) {
			System.out.print(list.get(i)+" ");
		}
	}
	private static void bfs(int i, int j) {
		Queue<Pos> qu = new LinkedList<>();
		qu.offer(new Pos(i,j));
		visited[i][j] = true;
		int index = 1;
		
		while(!qu.isEmpty()) {
			int size = qu.size();
			for(int q=0; q<size; q++) {
				Pos pos = qu.poll();
				
				for(int k=0; k<4; k++) {
					int x = pos.x + dx[k];
					int y = pos.y + dy[k];
					
					if(x<0 || x>=N || y<0 || y>=M || visited[x][y] || map[x][y] ==1) continue;
					
					qu.offer(new Pos(x,y));
					visited[x][y] = true;
					index++;
				}
			}
		}
		
		list.add(index);
	}
	
	static class Pos{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
}

정리

• 그림에 너무 신경 쓰지 말고 N, M의 배열을 선언해주고, 들어오는 도형 정보 영역을 1로 표현해주면 된다.
• BFS를 통해 방문 체크를 해주는데 아직 방문이 안된 곳이라면 새로운 영역에 해당되니깐 영역 개수++
• BFS로 새로운 값이 qu에 들어갈 때마다 영억의 넓이++;