Algorithm

백준[2583] - 영역 구하기

  • 문제: https://www.acmicpc.net/problem/2583
  • 분류: 그래프탐색, DFS
  • 난이도: S1
  • 소요시간: 15m
  • 자아성찰:
    •  
    • 요새 그래프 탐색 관련해서 모두 BFS로만 했던 것 같아 DFS 연습을 위해 골라봤다.
    • int[M][N] 순서가 불편해 N, M 순서로 바꾸어도 문제가 없을 것 같아 바꾸어 풀었다.
    • 최초 벽의 위치를 1로 마킹 -> 맵을 돌며 마킹 안한 부분부터 DFS 수행 -> dfs 호출 될 때마다 현재 영역 count++
    • 정석적인 DFS 풀이로 풀리는 문제이며, 상하좌우 이동에 대해서는 dx, dy 배열을 선언하는 게 편하다. 
    • 문득 stream을 써보고 싶어서 Collections.sort 말고 stream().sorted().forEach()로 결과를 출력했다.

 


 

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

public class B_2583 {

    static int M, N, K, cur;
    static int[] dx = {-1, 0, 1, 0}; // 상하좌우
    static int[] dy = {0, -1, 0, 1}; // 상하좌우
    static int[][] map;
    static ArrayList<Integer> result = new ArrayList<>();

    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[N][M];
        while (K-- > 0) {
            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 x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) { 
                    map[x][y] = 1; // 직사각형 위치 1로 마킹 (visited)
                }
            }
        }
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < M; y++) {
                if (map[x][y] == 0) { // 마킹 안된 영역부터 dfs 수행
                    cur = 0;
                    dfs(x, y);
                    result.add(cur); // 결과 저장
                }
            }
        }
        StringBuilder sb = new StringBuilder(String.valueOf(result.size())).append("\n"); // 결과 size 출력
        result.stream().sorted().forEach(n -> sb.append(n).append(" ")); // stream 만들고 sorted로 오름차순 정렬 후 forEach를 통해 출력
        System.out.println(sb);
    }

    public static void dfs(int x, int y) {
        cur++; // 방문했으니 현재 영역 크기 +1
        map[x][y] = 1; // 방문처리
        for (int n = 0; n < 4; n++) { // 상하좌우 방문
            int nx = x + dx[n];
            int ny = y + dy[n];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == 1) continue; // 맵 벗어남 or 이미 방문한 경우 스킵
            dfs(nx, ny); // dfs 재귀
        }
    }
}

 

'Algorithm' 카테고리의 다른 글

백준[2529] - 부등호  (0) 2024.05.22
백준[2638] - 치즈  (0) 2024.05.16
백준[2012] - 등수 매기기  (0) 2024.05.13
백준[11509] - 풍선 맞추기  (1) 2024.04.18
백준[15787] - 기차가 어둠을 헤치고 은하수를  (0) 2024.03.26