<Algorithm> 9. 2583번 영역구하기

2583번 영역구하기

• BFS나 DFS로 풀수 있는 기본 문제

• <http://willbfine.tistory.com/146> 좌표평면을 2차원배열로 옮기는 방법(핵심)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

public class Main {       static boolean[][] visited; // 방문확인     static int[][] graph; // 좌표평면 저장     static int area=0,N=0,M=0;        public static void main(String[] args) throws IOException {                  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));         String[] first=br.readLine().split(" ");          M=Integer.parseInt(first[0]);          N=Integer.parseInt(first[1]);          int T=Integer.parseInt(first[2]);                  graph=new int[N][M]; // 좌표평면의 x축 y축을 열,행 으로 변경          visited=new boolean[N][M];         ArrayList<Integer> res=new ArrayList<Integer>(); // 영역의 크기들 저장         int count=0;// 영역의 갯수                                    for(int g=0;g<T;g++){              String[] input=br.readLine().split(" ");                          int x1=Integer.parseInt(input[0]);            int y1=Integer.parseInt(input[1]);            int x2=Integer.parseInt(input[2]);            int y2=Integer.parseInt(input[3]);                                   for(int i=x1;i<x2;i++) {                for(int j=y1;j<y2;j++) { // 주어진 사각형 영역 1로 표시                   graph[i][j]=1;                }             }         }                         for(int i=0;i<graph.length;i++) {                for(int j=0;j<graph[i].length;j++) {                                           if(!visited[i][j]&&graph[i][j]==0) { // 값이 0이고 방문 안했을경우                                                     ck(i,j);                              count++; // 영역의 갯수 증가                             res.add(area+1); // 영역의 크기 저장                             area=0; //초기화                       }                }            }                        System.out.println(count);                      Collections.sort(res); // 영역의 크기 오름차순 정렬                        for(int i=0;i<res.size();i++) {                System.out.print(res.get(i)+" ");            }                                                    /* for(int i=graph[0].length-1;i>=0;i--) {  // 확인                for(int j=0;j<graph.length;j++) {                    System.out.print(graph[j][i]+" ");                }                System.out.println();            }*/                                    }          public static void ck(int i,int j) { // 영역의 크기 탐색           visited[i][j]=true;           graph[i][j]=2;                    if(i+1<N&&!visited[i+1][j]&&graph[i+1][j]==0) {               ck(i+1, j);               area++;           }           if(i-1>=0&&!visited[i-1][j]&&graph[i-1][j]==0) {               ck(i-1, j);               area++;           }           if(j+1<M&&!visited[i][j+1]&&graph[i][j+1]==0) {               ck(i, j+1);               area++;           }           if(j-1>=0&&!visited[i][j-1]&&graph[i][j-1]==0) {               ck(i, j-1);               area++;           }                         } } Colored by Color Scripter

cs

링크 https://www.acmicpc.net/problem/2583