[ Baekjoon ] #2583 영역 구하기

[Baekjoon][https://www.acmicpc.net/problem/2583]

 

기본적인 그래프 문제

풀이)

  (1) 이미지와 같이 노출을 하기 위해 m을 y축 n을 x 축으로 받아서 처리 : 배열 map[n][m]로 선언

  (2) 칠해진 직사각형 내 좌표의 값은 DFS 처리 시 해당 영역을 접근하지 않게끔 값 : '1'로 선언

  (3) 2번 내용 처리 시 아래 이미지와 같이 체크된 직사각형 영역은 1 그렇지 않은 부분은 0 으로 처리된다.

[ 2번 실행 시 map[n][m] 값을 출력 하면 위 그림과 같이 좌표의 값이 처리된걸 볼 수 있다. ]

   (4) DFS를 이용하여 이미 방문한 좌표와 (배열 visited[n][m] = 1) 과 좌표의 값이 1인 (map[n][m] = 1)

       부분을 제외하여 하나씩 값을 체크

 

map[n][m] : 배열로 직사각형 좌표 저장 // 1 : 빗줄 그어진 영역, 0 : 그 외

visited[n][m] : 이미 방문한 지역 저장 // 1 : 방문, 0 : 미방문

DFS 그래프로 <왼쪽, 위, 아래, 오른쪽 > 방향 이동

// int mx = x+xx[i]; int my = y+yy[i];

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

   static int n;
   static int m;
   static int k;
   static int[][] map;
   static int[][] visited;
   static int space;
   static int space_cnt;
   
   public static void main(String[] args) {
      // TODO Auto-generated method stub
      Scanner sc = new Scanner(System.in);
      
      m = sc.nextInt(); // y축
      n = sc.nextInt(); // x축
      k = sc.nextInt(); // 개수
      map = new int[n][m];
      visited = new int[n][m];
      
      for(int i=0; i<k; i++) {
         int start_y = sc.nextInt();
         int start_x = sc.nextInt();
         int end_y = sc.nextInt();
         int end_x = sc.nextInt();
         
         SetVisited(start_y, start_x, end_y, end_x);
      }
      
      ArrayList<Integer> ar_space_cnt = new ArrayList<Integer>();
      
      for(int i=0;i<m;i++) {
         for(int j=0;j<n;j++) {
            if(map[j][i] == 0 && visited[j][i] == 0) {
               space++;
               GetDfs(j, i);
               ar_space_cnt.add(space_cnt);
               space_cnt = 0;
            }
         }
      }
      
      Collections.sort(ar_space_cnt);
      
      System.out.println(space);
      if(ar_space_cnt.size() == 0 ) System.out.println("0");
      for(int i=0;i<ar_space_cnt.size();i++) {
         System.out.print(ar_space_cnt.get(i) + " ");
      }
   }
   
   // map[][] 색칠된 영역 1로 설정
   public static void SetVisited(int start_y, int start_x, int end_y, int end_x) {
      for(int i=start_y;i<end_y;i++) {
         for(int j=start_x;j<end_x;j++) {
        	 map[i][j] = 1;
         }
      }
   }
   
   // DFS 로직 처리
   public static void GetDfs(int x, int y) {
      visited[x][y] = 1;
      space_cnt++;

      int[] xx = {-1, 0, 1, 0};
      int[] yy = {0, 1, 0, -1};
      
      for(int i=0; i<4; i++) {
         int mx = x+xx[i];
         int my = y+yy[i];
         
         if(mx >=0 && mx < n && my >= 0 && my < m && map[mx][my] == 0 && visited[mx][my] == 0) {
        	 GetDfs(mx, my);
         }
      }
   }
}