[백준] 2667 단지번호붙이기 | DFS, BFS, 그래프 | 실버 Ⅰ | JAVA

⭐ 문제 분석

1. 지도는 N x N 크기의 정사각형 배열로 주어집니다. 각 셀은 0 또는 1로 이루어져 있습니다. 1은 집이 있는 곳을 나타내고, 0은 집이 없는 곳을 나타냅니다.
2. 연결된 집을 하나의 단지로 보고, 각 단지에 번호를 붙이면서 단지 내 집의 수를 세야 합니다.
3. 연결된 집은 좌우, 상하로 연결된 집을 의미하고, 대각선은 연결된 것으로 간주하지 않습니다.
4. 문제는 여러 개의 단지 수와 각 단지 내 집의 수를 오름차순으로 출력하는 것입니다.

⭐ 해결 전략

• DFS (깊이 우선 탐색): DFS는 재귀적 방법으로 현재 노드에서 연결된 모든 노드를 탐색하는 방법입니다. 여기서는 집이 연결된 영역을 탐색하기 위해 DFS를 사용하여 연결된 집들을 하나의 단지로 묶고, 각 단지의 크기를 구할 수 있습니다.
• 입력 처리 및 결과 출력: 지도 크기 N과 N개의 지도 데이터를 입력받고, DFS를 통해 각 단지의 집의 수를 구합니다. 이후 단지의 수와 각 단지 내 집의 수를 오름차순으로 출력하면 됩니다.

⭐ 풀이 과정

1. 입력 처리: 먼저 N을 입력받고, 그 다음 N개의 줄에 걸쳐 지도 데이터를 입력받습니다.
2. DFS 탐색: DFS를 사용해 각 집을 방문하면서 연결된 집들을 모두 방문하고, 그 집들이 속한 단지의 크기를 계산합니다.
3. 결과 저장 및 출력: 단지 내 집의 수를 리스트에 저장한 뒤, 오름차순으로 정렬하여 출력합니다.

 

 ✅ 정답 코드

import java.util.*;

public class Main {
    static int N; // 지도 크기
    static int[][] map; // 지도 배열
    static boolean[][] visited; // 방문 여부 배열
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 이동을 위한 배열
    static int[] dy = {0, 0, -1, 1};

    // DFS 함수: 현재 위치에서 연결된 집들을 탐색하며 단지 크기 구하기
    static int dfs(int x, int y) {
        visited[x][y] = true; // 현재 집을 방문 처리
        int houseCount = 1; // 현재 집은 하나의 집이므로 초기값 1
        
        // 상하좌우로 인접한 집들을 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 유효한 범위 내에 있고, 집이 있으며 아직 방문하지 않았다면
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 1 && !visited[nx][ny]) {
                houseCount += dfs(nx, ny); // 재귀적으로 집을 탐색
            }
        }
        
        return houseCount; // 단지 내 집의 수를 반환
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 지도 크기 입력
        N = sc.nextInt();
        sc.nextLine(); // 개행 문자 처리

        map = new int[N][N]; // 지도 초기화
        visited = new boolean[N][N]; // 방문 여부 초기화

        // 지도 입력 받기
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j) - '0'; // 문자 '0' 또는 '1'을 숫자 0 또는 1로 변환
            }
        }

        List<Integer> result = new ArrayList<>();
        
        // 모든 집을 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 집이 있고, 아직 방문하지 않았다면
                if (map[i][j] == 1 && !visited[i][j]) {
                    // DFS를 이용해 단지 내 집의 수를 구하고 리스트에 추가
                    result.add(dfs(i, j));
                }
            }
        }

        // 단지 수 출력
        System.out.println(result.size());
        
        // 각 단지 내 집의 수를 오름차순으로 정렬 후 출력
        Collections.sort(result);
        for (int count : result) {
            System.out.println(count);
        }
    }
}

🗒️ 코드 설명

1. 입력 처리:
   • N을 입력받고, 지도 데이터를 map 배열에 저장합니다.
2. DFS 구현:
   • dfs() 함수는 현재 위치에서 인접한 집들을 재귀적으로 탐색하면서 단지 내 집의 수를 세는 함수입니다. 4방향 상하좌우로 탐색을 진행합니다.
3. 결과 출력:
   • 단지를 발견할 때마다 해당 단지에 속한 집의 수를 result 리스트에 저장합니다.
   • 탐색이 끝난 후, 단지 수를 출력하고, 각 단지의 집의 수를 오름차순으로 정렬한 후 출력합니다.