[BOJ] 2667 - 단지번호붙이기(Java)

문제 설명

🔍 접근법

주어진 2차원 격자에서 집으로 이루어진 단지의 개수와 각 단지에 속한 집의 수를 오름차순으로 출력하는 문제입니다. 연결된 집은 상하좌우로 인접한 경우로 정의되며, 그래프 탐색 문제입니다.

문제를 보자마자 dfs로 해결할 수 있다는 생각이 들었습니다. 단지의 범위를 파악하려면, 한 집을 시작점으로 삼아 상하좌우로 연결된 모든 집을 탐색하며 방문 여부를 체크하고 집의 개수를 카운팅하면 됩니다. 최종적으로 단지 수와 각 단지의 집 수를 오름차순으로 출력해야 하므로, 이를 저장할 배열인 houseCnt를 선언해서 사용했습니다.

---

💻 코드

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

public class Main {
    static int[][] houseMap; //집 배치
    static boolean[][] visited; //방문여부
    static int sum, N; //입시 집 갯수 저장용
    static List<Integer> houseCnt = new ArrayList<>(); //단지수, 집 갯수

    //상, 하, 좌, 우
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};

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

        //집 배치 초기화
        for(int i=0; i<N; i++){
            String[] s = br.readLine().split("");
            for(int j=0; j<N; j++){
                if(Integer.parseInt(s[j]) == 1) houseMap[i][j] = 1;
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j] && houseMap[i][j] == 1){
                    sum=0; //단지 시작할때 sum 초기화
                    dfs(i,j);
                    houseCnt.add(sum);
                }
            }
        }

        Collections.sort(houseCnt);
        System.out.println(houseCnt.size()); //단지수 출력
        for(int cnt : houseCnt){
            System.out.println(cnt); //단지당 집 갯수 출력
        }
    }

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

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

            // 경계 체크
            if(newX >= 0 && newX < N && newY >= 0 && newY < N){
                if(!visited[newX][newY] && houseMap[newX][newY] == 1){
                    dfs(newX, newY);
                }
            }
        }
    }
}

---

💡 정리 및 느낀 점

• 이 문제는 DFS의 기본 개념을 이해하고 있다면 자연스럽게 접근할 수 있는 문제였습니다. 연결된 집을 탐색하며 단지를 구성하는 과정은 DFS의 핵심 로직과 잘 맞아떨어집니다.
• 상하좌우 인접 노드 탐색과 방문 여부 체크는 DFS/BFS 문제의 필수 요소입니다. 이 로직을 숙지하면 유사한 그래프 탐색 문제를 쉽게 풀 수 있습니다.
• DFS 구현에서 경계 조건(격자 범위 체크)과 방문 여부 조건만 정확히 처리하면 복잡한 문제도 체계적으로 해결 가능합니다. 재귀 호출의 흐름을 명확히 이해하는 것이 핵심입니다.
• 이번 문제를 통해 DFS의 재귀적 탐색 로직과 2차원 배열 처리에 대한 자신감이 생겼습니다. 앞으로는 BFS와의 비교나 최적화 가능성을 더 고민해보며 접근할 계획입니다.