2583_영역 구하기 **

사용 알고리즘: bfs

사용 언어: java

 

import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {
    static final int dx[] = {0,0,1,-1};
    static final int dy[] = {1,-1,0,0};
    static int n,m;
    static int map[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        for(int i=0; i<k; i++) {
            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 y=y1; y<y2; y++) {
                for(int x=x1; x<x2; x++){
                    map[y][x] = 9;
                }
            }
        }

//        for (int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(map[i]));
//        }

        ArrayList<Integer> areaCount = new ArrayList<>();
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j] == 0) {

                    int count = bfs(i,j);
                    areaCount.add(count);
                }
            }
        }

//        System.out.println("---------------------");
//        for (int i = 0; i < n; i++) {
//            System.out.println(Arrays.toString(map[i]));
//        }

        Collections.sort(areaCount); //오름차순 정렬

        sb.append(areaCount.size()).append('\n'); //Size = 영역의 개수
        for(int i : areaCount)  {
            sb.append(i + " ");
        }

        System.out.println(sb);
    }

    private static int bfs(int x, int y) {
        Queue<Point> q = new ArrayDeque<>();
        int cnt = 0;
        q.offer(new Point(x, y));
        map[x][y]++; //이거 안 해서 계속 1씩 크게 나왔다

        while (!q.isEmpty()) {
            Point p = q.poll();
            cnt++;
            for (int d = 0; d < 4; d++) {
                int nx = dx[d]+ p.x;
                int ny = dy[d]+ p.y;

                if(nx>=0 && nx<n && ny>=0 && ny<m) {
                    if(map[nx][ny] == 0) {
                        map[nx][ny] ++;
                        q.offer(new Point(nx, ny));
                    }
                }
            }
        }
        return cnt;
    }

//    static void dfs(int x, int y) {
//        square[x][y] = 1;
//        count ++; //영역의 개수 증가
//
//        for(int k=0; k<4; k++) {
//            int nx = x + dx[k];
//            int ny = y + dy[k];
//
//            if(0<=nx && nx<n && 0<=ny && ny < m) {
//                if(square[nx][ny] == 0) {
//                    dfs(nx,ny);
//                }
//            }
//        }
//    }

}

 

 

이슈:

- 와...... 로직은 맞았는데 왜 자꾸 틀렸지?

- bfs 돌릴 때 첫 시작 지점의 방문 처리를 하지 않아서 1씩 크게 나왔따...