[Baekjoon] 2583 - 영역 구하기

📝 문제

 

 

🔑 풀이 과정

· 이 문제는 DFS, BFS 어느 방법으로도 가능하다. 최근에 거의 BFS만 해서, 이번엔 DFS로 풀어봤다. (처음에 기억 안남 ㅋ)

 

· 이 문제는 DFS, BFS 문제를 좀 풀어봤다면 쉬울것이다. 그냥 연결요소의 개수를 구하는 문제라 생각하면 된다. 다만 이제 그 연결요소마다의 넓이를 구해야한다는게 추가됐다는 점?

 

· 풀이 과정

① K개의 직사각형의 양 꼭짓점 정보를 받으면서, 직사각형 내부는 값을 1로 바꿔준다.

② N * M 만큼 배열 전체탐색 하면서, 값이 0이고 (직사각형에 포함이 안되고) 방문하지 않은 곳을 발견하면 거기서 부터 DFS를 해준다. 한 번 DFS를 하면 그 영역이 탐색완료될 것이다.

③ 우리는 영역의 크기를 구해야 하므로, DFS 메서드가 한 번 수행될때 영역의 넓이를 하나씩 증가시키며 계산할 수 있게 해준다. (이 부분이 문제에서 제일 생각하기 까다로웠다. 변수의 선언 위치, 증감연산자 수행 위치, 초기화 등등...)

④ 영역의 개수는 따로 구해줄 필요 없이 영역의 크기가 들어간 ArrayList의 size를 출력하면 된다.

 

· 그리고 나는 문제의 그림에서 주어진 모양대로 하지않고, 모양을 조금 바꿔서 풀었다. 입력받을 때 x, y를 바꿔주기 귀찮았기 때문이다.

문제의 그림

내 그림

 

 

 

🔓 답안

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static int[][] arr;
    static boolean[][] visited;

    static int M;
    static int N;

    static int count; //각 영역의 넓이를 구할때 사용할 변수

    static ArrayList<Integer> result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        //입력
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); //열의 개수
        N = Integer.parseInt(st.nextToken()); //행의 개수
        int K = Integer.parseInt(st.nextToken()); //직사각형의 개수

        arr = new int[N][M];
        visited = new boolean[N][M];

        //각 직사각형의 양 꼭짓점 입력받기. 각 직사각형은 1로 채워주기
        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 j = x1; j < x2; j++){
                for(int k = y1; k < y2; k++){
                    arr[j][k] = 1;
                }
            }
        }

        result = new ArrayList<>(); //각 영역의 넓이를 추가할 ArrayList 생성
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if((arr[i][j] == 0) && (!visited[i][j])){ //배열을 전체순회하면서 0이고(직사각형이 아니고), 방문하지 않은 칸 발견시 카운트 증가후 거기서부터 DFS 수행
                    count = 0;
                    DFS(i, j);
                    result.add(count);
                }
            }
        }

        Collections.sort(result);

        //출력
        sb.append(result.size()).append("\n");
        for(int n : result){
            sb.append(n).append(" ");
        }


        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

    static void DFS(int x, int y){
        visited[x][y] = true;

        count++; //DFS가 수행될 때 마다 count 1 증가 (영역의 넓이를 구하는 것)

        for(int i = 0; i < 4; i++){
            int newX = x + dx[i];
            int newY = y + dy[i];

            if((newX >= 0) && (newX < N) && (newY >= 0) && (newY < M)){
                if((!visited[newX][newY]) && (arr[newX][newY] == 0)){
                    DFS(newX, newY);
                }
            }
        }

    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색