[백준] 단지번호붙이기 (2667번)

문제 흐름

1. 문제 목표
   • N x N 크기의 이진 행렬이 주어졌을 때, 1로 이루어진 연결된 집합(단지)을 찾아야 합니다.
   • 각 집합의 크기를 계산하여 총 단지 수와 단지별 집의 개수를 출력합니다.
   • 연결은 상하좌우 인접한 1들을 통해 이루어지며, 대각선 연결은 포함되지 않습니다.
2. 입력 설명
   • 첫 줄에 지도 크기 N이 주어집니다.
   • 이후 N개의 줄에 0과 1로 이루어진 행렬이 주어집니다. 1은 집이 있는 곳, 0은 빈 공간을 의미합니다.
3. 제약 조건
   • 최대 크기가 25x25인 행렬입니다.
   • 깊이 우선 탐색(DFS)을 사용해 모든 단지를 탐색하고 각 단지의 크기를 구합니다.

 

핵심 아이디어

• DFS(깊이 우선 탐색)를 사용해 한 번 방문한 집(1)은 다시 방문하지 않도록 방문 체크를 합니다.
• 단지 내의 집을 모두 탐색할 때마다 단지 크기를 계산하고 리스트에 저장합니다.
• 모든 좌표를 순회하며 새로운 단지가 발견될 때마다 탐색을 시작합니다.

 

알고리즘 흐름

1. 지도 초기화:
   • 입력받은 0과 1의 행렬을 저장합니다.
2. DFS 탐색:
   • 각 좌표를 순회하며 방문하지 않은 집(1)을 찾으면 DFS 탐색을 시작합니다.
   • 탐색 중 만나는 모든 집을 방문 처리하고 단지 크기를 증가시킵니다.
3. 결과 출력:
   • 단지의 개수와 각 단지의 집 개수를 출력합니다.
   • 단지 크기를 오름차순으로 정렬한 후 출력합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Main {

    static int n;  // 지도의 크기 (N x N)
    static int[][] map;  // 지도 정보를 저장할 2차원 배열
    static int count = 0;  // 현재 단지의 집 개수를 세기 위한 변수
    static boolean[][] visit;  // 방문 여부를 저장하는 배열

    // 상, 하, 좌, 우 방향 탐색을 위한 이동 좌표
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

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

        List<Integer> list = new ArrayList<>();  // 각 단지의 크기를 저장할 리스트
        n = in.nextInt();  // 지도 크기 입력
        in.nextLine();  // 개행 처리

        initGraph(in);  // 지도 초기화

        visit = new boolean[n][n];  // 방문 여부 배열 초기화

        // 모든 좌표를 순회하며 단지를 찾음
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 방문하지 않았고, 집이 있는 곳(1)을 발견한 경우
                if (!visit[i][j] && map[i][j] == 1) {
                    dfs(i, j);  // DFS 탐색으로 단지 크기 계산
                    list.add(count);  // 단지 크기 리스트에 추가
                    count = 0;  // 다음 단지를 위해 카운트 초기화
                }
            }
        }

        // 단지 개수 출력
        System.out.println(list.size());

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

    // DFS: 단지를 탐색하며 집의 개수를 셈
    public static void dfs(int x, int y) {
        visit[x][y] = true;  // 현재 좌표 방문 처리
        count++;  // 집의 개수 증가

        // 상하좌우 네 방향으로 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];  // 다음 X 좌표
            int ny = y + dy[i];  // 다음 Y 좌표

            // 유효한 범위 내에서, 방문하지 않았고 집이 있는 경우
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visit[nx][ny] && map[nx][ny] == 1) {
                dfs(nx, ny);  // 재귀 호출로 계속 탐색
            }
        }
    }

    // 지도 초기화: 입력받아 2차원 배열에 저장
    public static void initGraph(Scanner in) {
        map = new int[n][n];  // 지도 배열 초기화

        // 지도 정보 입력
        for (int i = 0; i < n; i++) {
            String[] s = in.nextLine().split("");  // 각 줄을 한 글자씩 분리
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(s[j]);  // 정수로 변환하여 저장
            }
        }
    }

    // (디버깅용) 지도 상태를 출력하는 메서드
    public static void viewGraph() {
        for (int[] arr : map) {
            System.out.println(Arrays.toString(arr));
        }
    }
}