99클럽 코테 스터디 34일차 - dfs

문제

영역 구하기

풀이

• 영역 개수 만큼 순회하며 주어진 좌표들을 기준으로 board[][]에 1을 채움
• board를 순회하면서 dfs로 영역의 개수를 카운팅

코드

import java.util.*;

public class Main {
    static int m, n, K;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1}; 
    static int[] dy = {1, -1, 0, 0};
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        m = scanner.nextInt();
        n = scanner.nextInt();
        K = scanner.nextInt();
        
        board = new int[m][n];
        visited = new boolean[m][n];
        
        for(int i = 0; i < K; i++){
            int startX = scanner.nextInt();
            int startY = scanner.nextInt();
            int endX = scanner.nextInt();
            int endY = scanner.nextInt();
            
            for(int j = startY; j < endY; j++){
                for(int l = startX; l < endX; l++){
                    board[j][l] = 1;
                }
            }
        }
        
        List<Integer> answer = new ArrayList<>();
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 0 && !visited[i][j]){
                    answer.add(dfs(i, j));
                }
            }
        }
        
        Collections.sort(answer);
        System.out.println(answer.size());
        for (int area : answer) {
           System.out.print(area + " ");
        }
    }
    
    private static int dfs(int x, int y) {
       visited[x][y] = true;
        int area = 1;
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && ny >= 0 && nx < m && ny < n && board[nx][ny] == 0 && !visited[nx][ny]){
                area += dfs(nx, ny);
            }
        }
        return area;
    }
}

정리

• 왜 모눈종이를 뒤집었지..? 찾느라 한참 걸림.. 뭔가 문제 해석이 더 어려움..
• 수능 문제 같음