[문제 풀이] 백준 2583번 영역 구하기 JAVA

문제

 

  문제접근 방법   

해당 문제는 m x n크기의 종이가 있다고 할 때 m, n, k를 입력받고 종이에 직사각형을 k 그리는데 직사각형의 왼쪽하단 값과 오른쪽 상단값이 주어져 직사각형을 이룬다. 이때 직사각형이 종이에 그려지면 직사각형을 제외한 나머지 구역들이 나누어지는데 

이 구역의 개수와 각각의 구역의 크기를 오름차순으로 출력하는 프로그램을 작성하는 문제이다.

먼저 처음접근은 섬크기를 나누는 문제와 유사하다는 생각이 들었다. 보통의 섬크기에서는 직사각형이 섬이고 나머지 빈구역들이 바다로 표현되지만 해당 문제에서는 반대로 생각하면 된다 직사각형은 접근할 수 없는 곳으로 설정하고 나머지 구역들의 크기를 구하면 되는 것이다. 이런 식으로 접근하여 작성한 코드는 아래와 같다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static List<Integer> list=new LinkedList<>();
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int m=s.nextInt();
        int n=s.nextInt();
        int k=s.nextInt();
        visited=new boolean[m][n];
        for(int i=0;i<k;i++){
            int x1=s.nextInt();
            int y1=s.nextInt();
            int x2=s.nextInt();
            int y2=s.nextInt();
            for(int y=y1;y<y2;y++){
                for(int x=x1;x<x2;x++){
                    visited[y][x]=true;
                }
            }
        }
        //System.out.println(Arrays.deepToString(visited));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j])bfs(i,j);
            }
        }
        
        StringBuilder sb=new StringBuilder();
        sb.append(list.size()).append("\n");
        Collections.sort(list);
        for(int i=0;i<list.size();i++){
            sb.append(list.get(i)+1).append(" ");
        }
        System.out.print(sb);
    }
    public static void bfs(int y,int x){
        Queue<int[]> q=new LinkedList<>();
        visited[y][x]=true;
        q.offer(new int[]{y,x});
        int dy[]={-1,1,0,0};
        int dx[]={0,0,-1,1};
        int xy[]=new int[2];
        int cnt=0;
        while(!q.isEmpty()){
            xy=q.poll();
            for(int i=0;i<4;i++){
                int ny=xy[0]+dy[i];
                int nx=xy[1]+dx[i];
                if(ny>=0&&nx>=0&&ny<visited.length&&nx<visited[0].length){
                    if(!visited[ny][nx]){
                        visited[ny][nx]=true;
                        q.offer(new int[]{ny,nx});
                        cnt++;
                    }
                }
            }
        }
        list.add(cnt);
    }
}

입력을 받은후 k개의 좌표를 받아 직사각형을 이루는 곳을 visited [][]=true로 설정하여 접근이 불가능하게 설정하고 

현재위치에서 상하좌우로 이동했을때 범위를 만족하고 방문한 적이 없다며 cnt를 카운트해 주어서 섬의 크기를 측정하였다.

또 모든 과정이 끝나고나면 list에 넣어주어 마지막에 list 크기를 출력하고 list를 오름차 순한 값에 1을 더해 출력해 준다.

여기서 1을 더해주는 이유는 처음 시작 칸을 카운트해주지 않기 때문이다. 본인처럼 1을 더하는 게 불편하다면 cnt값으 1로 설정하고 코드를 작성하여도 똑같은 결과를 얻을 수 있다.

 

  마무리  

해당 문제는 일반적으로 미로 찾기 문제나 섬 크기 문제에서 벽과 바다 즉, 모든 좌표값이 0과 1로 구성되어 제공되는 것과

달리 직사각형 부분을 직접 설정해줘 하는 문제였다.

이는 조금만 생각해 보면 위에서 설명한 것처럼 어렵지 않게 구현이 가능하고

이를 해결했다면 바다== 직사각형, 빈 공간 == 섬으로 접근해 구현이 가능하다.

또 많은 이들의 풀이를 확인해 본결과 대부분이 bfs 그리고 위에서 설명한 직사각형을 벽이라 가정하고 구현하였다.

다만 다른 점이 있다면 다른 이들의 풀이에서는 별도의 배열을 선언하는 방식이고 본인의 코드는 방문처리를 해버리는 방식이라는 차이가 존재하지만 알고리즘이나 코드상의 큰 차이는 존재하지 않았다.