99클럽 코테 스터디 34일차 TIL | 양 한마리... 양 두마리...

🖥️ 문제

얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" 정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

📝 풀이

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static List<Integer> areaSizes;
    static int currentAreaSize;
    static int rows;
    static int cols;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());
        int rectangleCount = Integer.parseInt(st.nextToken());

        visited = new boolean[rows][cols];
        areaSizes = new ArrayList<>();

        // 직사각형들의 영역을 방문 처리
        for (int i = 0; i < rectangleCount; i++) {
            st = new StringTokenizer(br.readLine());
            int startX = Integer.parseInt(st.nextToken());
            int startY = Integer.parseInt(st.nextToken());
            int endX = Integer.parseInt(st.nextToken()) - 1;
            int endY = Integer.parseInt(st.nextToken()) - 1;

            for (int y = startY; y <= endY; y++) {
                for (int x = startX; x <= endX; x++) {
                    visited[y][x] = true;
                }
            }
        }

        // 영역 탐색
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                if (!visited[y][x]) {
                    currentAreaSize = 0;
                    dfs(y, x);
                    areaSizes.add(currentAreaSize);
                }
            }
        }

        // 결과 출력
        Collections.sort(areaSizes);
        StringBuilder sb = new StringBuilder();
        sb.append(areaSizes.size()).append("\n");
        for (int size : areaSizes) {
            sb.append(size).append(" ");
        }
        System.out.print(sb);
    }

    static void dfs(int y, int x) {
        visited[y][x] = true;
        currentAreaSize++;

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

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

            if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && !visited[ny][nx]) {
                dfs(ny, nx);
            }
        }
    }
}

이 문제는 2D 평면에서 연결된 영역을 찾는 문제다. 나는 BFS를 사용해서 연결한 양 무리를 탐색했고, 큐 자료구조를 활용해서 풀었다.

먼저 각 테스트에 대해 그리드를 순회하고 #이고 아직 방문하지 않은 위치를 찾는다. 방문하지 않았다는 것은 새로운 양 무리가 시작된 것이라 카운트를 하나 증가켰다.

그리고 이 위치에서 BFS를 시작하여 연결된 모든 #을 방문 처리했다. 탐색 시에는 초기 양의 위치에 큐를 넣고, 큐가 빌 때까지 인접한 모든 양을 큐에 추가하여 방문을 표시했다.