[BOJ] 백준 2583번 영역 구하기 자바(java) 풀이 (dfs, bfs)

BOJ 2583번 영역 구하기 문제 자바(java) 풀이

• 난이도: 실버1
• 풀이시간: 30분
• 백준 2583번 영역 구하기
  
  
  

문제정리

1. MxN 크기의 모눈종이가 주어진다.
2. 모눈 종이 위에 K개의 직사각형을 그린다.
3. k개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
4. 몇개의 영역으로 분리되는지, 각 영역의 넓이는 어떤지 구하여라
   
   
   

문제풀이

1. 분리된 영역과 넓이를 구하는 것이므로 모든 좌표에서 bfs 탐색을 하면 됩니다.
   이 문제는 영역을 구분짓는 문제인 보물섬, 치즈, 빙산과 유사합니다.
2. 문제에서 주어지는 직사각형의 좌표들과 배열의 인덱스가 다르기 때문에 주어진 x,y좌표를 반대로 바꿔줍니다. ( 바꾸면 답이 잘 나오는지 직접 그려보느라 시간 좀더 걸림 )
3. 직사각형이 있는 곳은 map에 1로 표시합니다.
4. 그리고 유효한 인덱스이며 map에 1로 표시되어있지 않은곳만 방문하며 영역의 넓이를 구합니다.
5. Collections.sort를 이용하여 오름차순 정렬합니다.
6. 영역의 개수는 bfs 함수를 부른 횟수로 계산할 수 있습니다.
   dfs나 bfs 상관 없이 통과할 수 있습니다.
   
   
   

BOJ 2583번 영역 구하기 자바 코드

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Queue;
	import java.util.LinkedList;
	import java.util.Collections;
	import java.util.ArrayList;
	class Pos {
	int x;
	int y;
	Pos(int x, int y){
	this.x = x;
	this.y = y;
	}
	}
	class Main {
	static int width, height, K;
	static int[][] map;
	// 상하좌우
	static int[] xdir = {-1,1,0,0};
	static int[] ydir = {0,0,-1,1};
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String[] temp = br.readLine().split(" ");
	height = Integer.parseInt(temp[0]);
	width = Integer.parseInt(temp[1]);
	K = Integer.parseInt(temp[2]);
	map = new int[height][width];
	// 직사각형 정보 (왼쪽 아래, 오른쪽 위)
	// X,y 좌표를 뒤집어야 함 => 왼쪽 위, 오른쪽 아래
	for(int i=0; i<K; i++){
	temp = br.readLine().split(" ");
	int y1 = Integer.parseInt(temp[0]);
	int x1 = Integer.parseInt(temp[1]);
	int y2 = Integer.parseInt(temp[2]);
	int x2 = Integer.parseInt(temp[3]);
	for(int j=x1; j<x2; j++){
	for(int k=y1; k<y2; k++){
	map[j][k] = 1;
	}
	}
	}
	int area=0;
	ArrayList<Integer> list = new ArrayList<>();
	for(int i=0; i<height; i++){
	for(int j=0; j<width; j++){
	if(map[i][j] != 1){
	list.add(bfs(i,j));
	area++;
	}
	}
	}
	Collections.sort(list);
	System.out.println(area);
	for(int a : list){
	System.out.print(a + " ");
	}
	System.out.println();
	br.close();
	}
	private static int bfs(int a, int b){
	Queue<Pos> q = new LinkedList<>();
	int sum = 0;
	q.add(new Pos(a,b));
	map[a][b] = 1;
	while(!q.isEmpty()){
	Pos p =q.poll();
	int x = p.x;
	int y = p.y;
	for(int i=0; i<4; i++){
	int dx = x + xdir[i];
	int dy = y + ydir[i];
	if(isValidPosition(dx, dy) && map[dx][dy] != 1){
	q.add(new Pos(dx, dy));
	map[dx][dy] = 1;
	sum++;
	}
	}
	}
	return sum+1;
	}
	private static boolean isValidPosition(int x, int y){
	if( x < 0 || x >= height || y < 0 || y >= width) return false;
	return true;
	}
	}

view raw BOJ2583.java hosted with ❤ by GitHub