[백준/JAVA] 2583번: 영역 구하기

🔺 문제

2583번: 영역 구하기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int M, N, K, cnt;
    static int[][] map;
    
    static PriorityQueue<Integer> list = new PriorityQueue<>();    // 각 영역 넓이 저장 리스트
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        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());
        
        map = new int[M][N];
        
        while(K --> 0) {
            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());
            
            // 🔔 직사각형이 만들어지는 영역은 방문 처리 🔔
            for(int j = y1 ; j < y2 ; j++) {
                for(int i = x1 ; i < x2 ; i++) {
                    map[j][i] = -1;
                }
            }
        }
        
        for(int i = 0 ; i < M ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(map[i][j] == 0) {
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        
        sb.append(cnt).append("\n");
        while(!list.isEmpty()) {
            sb.append(list.poll()).append(" ");
        }
        System.out.println(sb);
    }
    
    private static void bfs(int a, int b) {
        if(map[a][b] != 0) return;
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {a,b});
        map[a][b] = -1;    // 방문 표시
 
        int area = 0;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            area++; // 영역 넓이 + 1
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || ny < 0 || nx >= M || ny >= N || map[nx][ny] == -1) continue;
 
                queue.add(new int[] {nx, ny});
                map[nx][ny] = -1;    // 방문 표시
            }
        }
        list.add(area); // 넓이 리스트에 각 영역 넓이 추가
    }
}

✅ 해결 아이디어
✔ BFS / DFS
- 각 영역의 넓이들을 저장할 리스트를 우선순위 큐로 만들어 자동 오름차순 정렬하게 했다. 
(그냥 list.sort(null) 이나 Collections.sort(list) 해도 된다.)

 

💥 유의사항

• Line 32-36  ⇨  for문 j, i 순서 주의해야 한다... (y 먼저 !)

 

 

---

🔺 다른 풀이들

- DFS 풀이

https://www.acmicpc.net/source/56170643

https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2583%EB%B2%88-%EC%98%81%EC%97%AD-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%9E%90%EB%B0%94Java

 

---

💬 느낀 점

cnt 안 구하고 list.size() 출력해도 됨!!

 

32-36번째 줄.. x랑 y 순서 바꿔서 해서 계속 틀렸었음...ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔

https://dding9code.tistory.com/6

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