[백준] 알고리즘 분류(그래프 탐색,JAVA)2583번, 영역 구하기

문제 링크

2583번: 영역 구하기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 모눈종이에 K개의 직사각형을 채웁니다.

2. 직사각형으로 나누어진 영역의 개수와 각 영역의 넓이를 오름차순 정렬하여 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 직사각형 부분을 채운 뒤 BFS탐색으로 영역을 탐색합니다.

 

3. 영역의 개수와 각 영역의 넓이를 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

M : 5

N : 7

K : 3

 

(0, 2), (4, 4)

(1, 1), (2, 5)

(4, 0), (6, 2)

 

2. 직사각형 부분을 채운 뒤 BFS탐색으로 영역을 탐색합니다.

 

직사각형 채우기

	2
1	1, 2	1	1
1	1, 2	1	1
	2			3	3
				3	3

 

BFS 탐색으로 영역 나누기.

영역1.	2	영역2.	영역2.	영역2.	영역2.	영역2.
1	1, 2	1	1	영역2.	영역2.	영역2.
1	1, 2	1	1	영역2.	영역2.	영역2.
영역3.	2	영역3.	영역3.	3	3	영역2.
영역3.	영역3.	영역3.	영역3.	3	3	영역2.

 

 

3. 영역의 개수와 각 영역의 넓이를 결과로 출력합니다.

 

영역의 개수 : 3개

영역의 넓이 : 1(영역1), 7(영역2), 13(영역3)

 

3

1 7 13

을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 직사각형의 정보를 띄어쓰기 기준으로 나누었습니다.
• fillArr을 통해서 K개의 직사각형의 형태만큼 모눈종이를 채웠습니다.
• bfs함수를 이용하여 직사각형으로 나누어진 각 영역을 탐색합니다.
• 각 영역의 넓이를 Collections.sort를 이용하여 오름차순으로 정렬하였습니다.
• 영역의 개수와 각 영역의 넓이를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• fillArr함수는 직사각형의 정보를 이용하여 모눈종이에 채웁니다.
• bfs함수는 BFS으로 모눈종이의 각 영역을 탐색합니다.
• inSpace함수는 BFS탐색시 모눈종이에 벗어나는지 확인합니다.

 

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


public class Main {
    //모눈종이 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int M,N,K;
    static boolean[][] arr, visited;	//모눈종이 정보 및 방문 확인 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    static ArrayList<Integer> answer = new ArrayList<>();	//영역의 넓이 저장 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new boolean[M][N];
        //직사각형 정보 저장 및 채우기
        for(int i=0;i<K;i++){
            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());
            fillArr(x1, y1, x2, y2);
        }
        visited = new boolean[M][N];
        int count = 0;
        //BFS탐색으로 각 영역 구하기
        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(!arr[i][j] && !visited[i][j]){
                    bfs(i, j);
                    count++;
                }
            }
        }
        Collections.sort(answer);	//영역의 넓이 오름차순 정렬
        bw.write(count + "\n");		//영역의 개수 BufferedWriter 저장
        //각 영역의 넓이 BufferedWriter 저장
        for (Integer integer : answer)
            bw.write(integer + " ");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    static void fillArr(int x1, int y1, int x2, int y2){
        for(int i=y1;i<y2;i++){
            for(int j=x1;j<x2;j++){
                arr[i][j] = true;
            }
        }
    }
    //모눈종이를 BFS탐색하여 각 영역을 나누는 함수
    static void bfs(int y, int x){
        Queue<position> q = new LinkedList<>();
        q.add(new position(x, y));
        visited[y][x] = true;
        int width = 1;
        while(!q.isEmpty()){
            position cur = q.poll();
            //인접한 공간 탐색
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                //직사각형이 채워지지 않은 영역일 때
                if(inSpace(tempX,tempY) && !visited[tempY][tempX] && !arr[tempY][tempX]){
                    q.add(new position(tempX,tempY));
                    width++;
                    visited[tempY][tempX] = true;
                }
            }
        }
        answer.add(width);	//현재 영역 저장
    }
    //BFS탐색에서 이동시 모눈종이에 영역에 있는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x>=0 && y>=0 && y< M && x < N)
            return true;
        return false;
    }
}