99클럽 코테 스터디 18일차 TIL - [백준] 단지번호붙이기 (Java)

📌 오늘의 학습 키워드

[백준] 단지번호붙이기 (Java)
https://www.acmicpc.net/problem/2667

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 첫 번째 줄 -지도의 크기 N (가로/세로 동일, 5 ≤ N ≤ 25)
N 번째 줄 - N개의 자료(0 또는 1)
출력 : 첫 번째 줄 - 총 단지수
두 번째 줄부터 - 각 단지내 집의 수를 오름차순으로 정렬해 하나씩 출력

가능한 시간복잡도

O(n^2)
n : 그리드 크기

알고리즘 선택

DFS

📌 코드 설계하기

1. 격자의 크기 n을 입력받고, n개의 줄을 입력받아 각 줄을 n개의 정수로 변환하여 2차원 배열에 저장한다.
   int[][] map: 입력받은 그리드를 저장할 2차원 정수 배열
   boolean[][] visited: 각 위치의 방문 여부를 기록하는 불리언 배열
   ArrayList complexSizes: 각 단지의 크기를 저장할 리스트
2. 네 방향(상, 하, 좌, 우)을 탐색하기 위한 방향 벡터를 설정한다.
3. DFS는 현재 위치에서 시작하여 연결된 모든 1을 방문하며, 단지의 크기를 센다. 상하좌우 방향으로 이동하며 아직 방문하지 않은 1을 재귀적으로 탐색한다.
4. 격자의 모든 위치를 탐색하며, 방문하지 않은 1이 발견되면 새로운 단지를 발견한 것으로 간주하고 DFS를 수행한다.
5. DFS 호출 후 단지의 크기를 complexSizes 리스트에 추가한다. 모든 단지의 크기를 complexSizes 리스트에 저장한 후 오름차순으로 정렬한다.
6. 총 단지의 수와 각 단지의 크기를 출력합니다

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Main {
    static int n; // 그리드의 크기
    static int[][] map; // 그리드 맵
    static boolean[][] visited; // 방문 체크를 위한 배열
    static int[] dx = {1, -1, 0, 0}; // x 방향 이동 (오른쪽, 왼쪽)
    static int[] dy = {0, 0, 1, -1}; // y 방향 이동 (아래, 위)
    static int count; // 현재 단지에 포함된 집의 수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        map = new int[n][n];
        visited = new boolean[n][n];

        // 그리드 입력 받기
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        ArrayList<Integer> complexSizes = new ArrayList<>(); // 단지 크기를 저장할 리스트

        // 모든 위치에 대해 DFS 실행
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    count = 0; // 새로운 단지를 탐색 시작
                    dfs(i, j);
                    complexSizes.add(count); // 탐색이 끝난 후 단지 크기 추가
                }
            }
        }

        Collections.sort(complexSizes); // 단지 크기를 오름차순으로 정렬

        System.out.println(complexSizes.size()); // 총 단지 수 출력
        for (int size : complexSizes) {
            System.out.println(size); // 각 단지의 크기 출력
        }
    }

    // DFS를 사용하여 단지 탐색
    static void dfs(int x, int y) {
        visited[x][y] = true; // 현재 위치 방문 체크
        count++; // 집의 수 증가

        // 네 방향 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 그리드 범위 안에 있는지 확인하고, 방문하지 않았으며 집이 있는 곳(1)인지 확인
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (!visited[nx][ny] && map[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }
}