[99클럽 코테 스터디] 35일차 TIL DFS/BFS

 

 

오늘의 문제는 백준

 

2583번 영역 구하기

 

 

문제

 

 

문제 설명 

M x N 크기의 모눈 종이 안에 세 개의 직사각형이 들어있습니다. 이 때 직사각형을 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지고 그 영역의 넓이가 얼마인지 구하는 문제입니다. 

[입력]

첫 번째 줄 : 100 이하의 자연수 M, N, k가 빈 칸을 사이에 두고 차례로 주어집니다. 

다음 줄 : 직사각형의 왼쪽 아래 꼭지점의 x, y 좌표값과 오른쪽 꼭지점의 x,y 좌표값이 빈 칸을 사이에 두고 주어집니다. 

[출력] 

첫째 줄 : 분리되어 나누어지는 영역의 개수를 출력합니다.

둘째 줄 : 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력합니다. 

 

[입력 예시]

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

[출력 예시]

3
1 7 13

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 60분이 걸렸습니다.

 

 

 

문제 접근 방식

먼저 입력받은 모눈종이를 나타낼 2차원 배열 map을 생성하고 초기 값을 0으로 초기화합니다. 입력 받은 직사각형의 시작 좌표와 끝 좌표까지의 범위를 1로 채웁니다. 모눈 종이를 순회하며 값이 0인 칸이 발견되면 BFS 알고리즘을 사용해 연결된 모든 빈 칸을 탐색하고 넓이를 계산해 리스트에 추가합니다. 

 

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
    private static int M, N, k;
    private static int startX, startY, endX, endY; 
    private static int[][] map;

    public static void square(int x1, int y1, int x2, int y2) {
        for(int i = y1; i < y2; i++) {
            for(int j = x1; j < x2; j++) {
                map[i][j] = 1;
            }
        }
    }
  
    public static int bfs(int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{m, n});
        map[m][n] = 1; 

        int blank = 1; 

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

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

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

                if(nx >= 0 && nx < M && ny >= 0 && ny < N && map[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny});
                    map[nx][ny] = 1;
                    blank++;
                }
            }
        }
        return blank; 
    }
    
    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];
        
        for(int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            startX = Integer.parseInt(st.nextToken());
            startY = Integer.parseInt(st.nextToken());
            endX = Integer.parseInt(st.nextToken());
            endY = Integer.parseInt(st.nextToken());

            square(startX, startY, endX, endY);
        }

        List<Integer> answer = new ArrayList<>();

        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 0) {
                    answer.add(bfs(i, j));
                }
            }
        }

        Collections.sort(answer);

        System.out.println(answer.size());
        for(int answers : answer) {
            System.out.print(answers + " ");
        }

        
    }
}

 

 

 

 

 

 

 

 

이렇게 오늘 35일차 TIL을 작성해 보았습니다.