[백준] 2583 영역 구하기 - BFS(넓이우선탐색) JAVA

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

코드설명

 BFS(넓이우선탐색) 를 활용합니다.

 

먼저, coloring 함수를 통해서 각 영역에 해당하는 구간을 색칠합니다.

이때, 유의할점은 일반적으로 행열의 순서로 주어진 것이 아닌 열행의 길이로 주어졌습니다.

그 부분만 유의한다면 크게 어려운 문제는 아닙니다.

 

두번째로, BFS로 색칠하여 각 분리된 영역을 구합니다.

BFS구현시 놓칠 수 있는점은, 첫 BFS에 큐를 넣을떄 방문처리를 까먹지 않고 해줘야 한다는 점입니다.

그래야만, 시간위치에 중복방문하는 일이 없겠지요.

static int BFS(int sr, int sc) {
    Queue<int[]> q = new LinkedList<>();
    int ret = 0;
    q.offer(new int[] {sr, sc});
    matrix[sr][sc] = true;
    while(!q.isEmpty()) {

코드

package Main;
 
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 {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static boolean[][] matrix = new boolean[101][101];
	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());
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());
			coloring(sx, sy, ex, ey);
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(matrix[i][j] == false) {
					pq.offer(BFS(i, j));
				}
			}
		}
		System.out.println(pq.size());
		while(!pq.isEmpty()) System.out.print(pq.poll()+" ");
		
	}
	static int BFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		int ret = 0;
		q.offer(new int[] {sr, sc});
		matrix[sr][sc] = true;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			ret += 1;
			for(int[] dir : new int[][] { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }) {
				int nr = temp[0] + dir[0];
				int nc = temp[1] + dir[1];
				if(nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
				if(matrix[nr][nc] == true) continue;
				q.offer(new int[] {nr, nc});
				matrix[nr][nc] = true;
			}
		}
		return ret;
	}
	static void coloring(int sx, int sy, int ex, int ey) {
		for(int i=sx; i<ex; i++) {
			for(int j=sy; j<ey; j++) {
				matrix[j][i] = true;
			}
		}
	}
}