자바(백준) 2583 영역 구하기

새로 알게 된 점 & 오답 노트

해당 문제를 처음에는 dfs로 문제를 풀어보았다. 하지만 이번에 문제집을 밀면서 있길래 bfs로 풀어보자라는 생각이 들어서 bfs로 풀었다. 6달 만에 본 문제여서 아예 풀이법이 생각이 나지 않아 처음 본 문제처럼 풀었다. 

 

헷갈렸던 부분이 일단 x, y좌표이다. 아무 생각 없이 이 문제 쉽다 하고 원래의 x, y좌표대로 하면 바로 틀리기 때문이다. 여기서는 행이 y이고 열이 x이기 때문에 생각하면서 입력을 받아야 한다.

 

그리고, 분명히 좌표는 7까지 있는데, index크기는 6까지 있다. 그러면 Index 예외가 생기지 않을까라는 생각이 들었다. 그러나 직사각형이 차지하는 부분을 색칠하면서 끝점들은 포함하지 않기 때문에 이 부분은 자동적으로 제외할 수 있다.

 

---

코드

package BFS;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int row, col, num;
    static int arr[][];
    static boolean visit[][];
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        ArrayList<Integer> al = new ArrayList<>();
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
        num = atoi(st.nextToken());
 
        arr = new int[row+1][col+1];
        visit = new boolean[row+1][col+1];
 
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                arr[i][j] = 1;
            }
        }
 
        for(int i = 0; i < num; i++){
            st = new StringTokenizer(br.readLine());
            int y1 = atoi(st.nextToken());
            int x1 = atoi(st.nextToken());
            int y2 = atoi(st.nextToken());
            int x2 = atoi(st.nextToken());
            for(int j = x1; j < x2; j++){
                for(int k = y1; k < y2; k++){
                    arr[j][k] = 0;
                }
            }
        }
 
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(!visit[i][j] && arr[i][j] == 1){
                    al.add(bfs(i, j));
                }
            }
        }
 
        Collections.sort(al);
 
        System.out.println(al.size());
        for(int index : al){
            System.out.print(index + " ");
        }
 
    }
    static int bfs(int x, int y){
        int dx[] = {-1,1,0,0};
        int dy[] = {0,0,1,-1};
        Queue<AreaPoint> q = new ArrayDeque<>();
        visit[x][y] = true;
        q.offer(new AreaPoint(x, y));
        int count = 1;
        while(!q.isEmpty()){
            AreaPoint ap = q.poll();
            for(int i = 0; i < 4; i++){
                int X = ap.x + dx[i];
                int Y = ap.y + dy[i];
 
                if(!isRangeTrue(X, Y)) continue;
                if(visit[X][Y]) continue;
 
                if(arr[X][Y] == 1){
                    q.offer(new AreaPoint(X, Y));
                    visit[X][Y] = true;
                    count++;
                }
            }
        }
        return count;
    }
    static boolean isRangeTrue(int x, int y){
        return x >= 0 && x < row && y >= 0 && y < col;
    }
}
 
class AreaPoint{
    int x, y;
 
    AreaPoint(int x, int y){
        this.x = x;
        this.y = y;
    }
}