[JAVA] 백준 2583 - 영역구하기 ( BFS + 구현 )

www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

- 사각형 칠하기

위와 같이 m=5 이고 n=7인 배열에서 왼쪽 아래 좌표(0,2) 와 오른쪽 위 좌표(4,4) 를 가지고 사각형에 해당되는 부분은 어떻게 체크 할것인가?

 

<그림1> 의 전체 큰 배열의 이름을 arr 라고 하자.

(0,2) 와 (4,4)가 주어졌을 때 결과적으로 체크 되는 부분은 다음과 같다.

 

arr[1][0] , arr[1][1] , arr[1][2] , arr[1][3]

arr[2][0] , arr[2][1] , arr[2][2] , arr[2][2]   

 

 

arr는 왼쪽 위가 [0][0] 이지만 문제에서 (0,0)은 왼쪽 아래이다.

왼쪽 아래가 기준인 점을 왼쪽 위가 기준이 되도록 바꿔야한다.

 

 

체크 되는 부분의 "열" 의 범위는 왼쪽 아래 좌표의 0보다 같거나 크고 오른쪽 위 좌표의 4보다 작다.

arr 의 열의 체크 범위는 0<= 열 < 4 이다.

 

체크 되는 부분의 "행" 의 범위는 (m - 오른쪽 위의 4) 보다 같거나 크고 (m - 왼쪽 아래 2) 보다 작다.

arr 의 행의 체크 범위는 m-4 <= 행 < m-2 이다. (이때 m=5)

 

위를 좀더 일반화 해보자.

 

왼쪽 아래 좌표를 (x1,y1) 오른쪽 위 좌표를 (x2,y2) 라고 할 때,

배열에서 채워야 하는 부분은 아래 코드 처럼 정리 할 수 있다.

for(int i=m-y2;i<m-y1;i++){
            for(int j=x1;j<x2;j++) {
                arr[i][j] = true;
            }
 }

 

위 로직을 이용해 깔끔하게 함수로 만들면 

 

public static void fillArr(int x1,int y1,int x2,int y2){
        for(int i=m-y2;i<m-y1;i++){
            for(int j=x1;j<x2;j++) {
                arr[i][j] = true;
            }
        }
 }

 

 

- BFS 로 영역의 개수를 카운트 하면서 영역의 넓이 구하기

만약 (x,y)가 사각형의 일부가 아니고(arr[x][y] = false) 방문한적이 없다면(visited[x][y] = false) 아래의 함수를 실행한다.

 

dx , dy 는 4방향으로 체크하기 위한 것으로 (x,y) 를 기준으로 (x+1,y),(x-1,y),(x,y+1),(x,y-1) 을 탐색한다.

 

areas 는 영역의 넓이들을 모은 리스트이다.

 

 

public static void bfs(int x,int y){
        int area = 1;
        Queue<Point> q  = new LinkedList<>();
        visited[x][y] = true;
        q.add(new Point(x,y));

        while(!q.isEmpty()){
            Point p = q.poll();

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(0<= nx && nx<m && 0<=ny && ny < n && !arr[nx][ny] && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.add(new Point(nx,ny));
                    area++;
                }
            }
        }

        areas.add(area);
 }
 static class Point{
        public int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
 }
    
    
   

 

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n,m,k;
    static boolean[][] arr = new boolean[101][101];
    static boolean[][] visited = new boolean[101][101];
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int ans = 0;
    static ArrayList<Integer> areas = new ArrayList<>();


    public static void main(String[] args) throws Exception {

        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());

        int x1,y1,x2,y2;

        for(int i=0;i<k;i++){
            st  = new StringTokenizer(br.readLine());
            // left down
            x1 = Integer.parseInt(st.nextToken()); y1 = Integer.parseInt(st.nextToken());
            // right up
            x2 = Integer.parseInt(st.nextToken()); y2 = Integer.parseInt(st.nextToken());

            fillArr(x1,y1,x2,y2);

        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j] && !arr[i][j]) {
                    bfs(i, j);
                    ans++;
                }

            }
        }

        System.out.println(ans);
        Collections.sort(areas);
        for(int a : areas) System.out.print(a + " ");
        

    }

    public static void fillArr(int x1,int y1,int x2,int y2){
        for(int i=m-y2;i<m-y1;i++){
            for(int j=x1;j<x2;j++) {
                arr[i][j] = true;
            }
        }
    }

    public static void bfs(int x,int y){
        int area = 1;
        Queue<Point> q  = new LinkedList<>();
        visited[x][y] = true;
        q.add(new Point(x,y));

        while(!q.isEmpty()){
            Point p = q.poll();

            for(int i=0;i<4;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(0<= nx && nx<m && 0<=ny && ny < n && !arr[nx][ny] && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q.add(new Point(nx,ny));
                    area++;
                }
            }
        }

        areas.add(area);
    }

    static class Point{
        public int x,y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}