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

 

오늘은 백준 2667번 단지번호 붙이기 문제를 풀면서 DFS(깊이 우선 탐색)를 활용한 풀이를 정리해보려고 한다.

---

📝 문제 개요

정사각형 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳을 의미한다.
상하좌우로 연결된 집들을 하나의 단지(Connected Component) 로 간주하고,
각 단지 내 집의 개수를 오름차순으로 출력하는 문제다.

입력 예시

편집

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000

출력 예시

3

7

8

9

---

🔍 접근 방법

1️⃣ 2차원 배열을 활용하여 지도 표현

입력값을 N × N 크기의 2차원 배열 arr에 저장한다.
문자열을 charAt(j) - '0'을 이용해 int 값으로 변환해서 저장한다.

2️⃣ DFS를 사용하여 연결된 단지 탐색

지도 전체를 탐색하며, 방문하지 않은 집(1) 이 발견되면 DFS를 실행한다.
DFS는 재귀를 활용하여 상하좌우로 연결된 모든 집을 탐색하고, 방문한 집을 visited 배열에 기록한다.

3️⃣ 각 단지의 크기 저장 및 정렬

DFS를 실행할 때마다 집의 개수를 카운트하고 리스트에 저장한 뒤, 결과를 오름차순으로 정렬한다.

---

💻 코드 구현 (DFS 활용)

package Boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Boj2667 {
    static int[][] arr;
    static boolean[][] visited;
    static int N, count = 0;
    static ArrayList<Integer> result = new ArrayList<>();

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    dfs(i, j);
                    result.add(count);
                }
            }
        }

        Collections.sort(result);
        System.out.println(result.size());
        for (int r : result) {
            System.out.println(r);
        }
    }

    static int 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];

            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if (arr[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
        return count;
    }
}

---

🛠 코드 개선 및 디버깅 과정

💡 초기 코드에서 발생한 문제점
1️⃣ arr = new int[N+1][N+1]로 선언하여 배열 크기가 불필요하게 커짐 → arr = new int[N][N]로 수정
2️⃣ dfs() 내에서 count++를 중복 수행하여 잘못된 단지 크기 계산 → count += dfs(nx, ny);로 수정
3️⃣ 입력 처리 오류: read() 대신 readLine()을 사용하여 문자열을 한 줄씩 읽도록 수정

---

📌 결과 정리

✅ DFS(깊이 우선 탐색) 을 활용하여 연결된 단지를 탐색하고 개수를 구하는 문제였다.
✅ 재귀 호출 시 count를 반환하여 누적하는 방식을 사용하여 개수를 정확히 계산할 수 있었다.
✅ 배열 크기 조정, 방문 여부 체크, 정렬 과정까지 모두 반영하여 최적화했다.

🚀 오늘도 하나의 알고리즘 문제를 해결하며 DFS에 대한 이해를 더욱 깊게 다질 수 있었다!
🔥 다음엔 BFS(너비 우선 탐색) 을 활용한 방식도 한 번 풀어봐야겠다. 😊