[DFS로 탐색하기] 백준 2667번 JAVA : 단지 번호 붙이기

2차원 배열에서 특정 조건을 만족하는 영역(1)을 찾아내고, 해당 영역의 크기를 세는 문제를 해결할 때 DFS(깊이 우선 탐색)를 활용할 수 있다. 이 과정에서 탐색이 진행되는 동안 방문한 노드는 처리하여 중복 방문을 방지하고, 단지의 크기를 반환하는 방식으로 구현한다.

 

문제 정의

예를 들어, 7x7 크기의 2차원 배열이 있다고 가정한다. 배열은 0과 1로 구성되며, 1은 단지의 일부를 나타낸다. 이때, 서로 연결된 1들을 하나의 단지로 간주하고 각 단지의 크기를 구해야 한다.

입력 배열은 다음과 같다고 가정한다.

 

0110100  
0110101  
1110101  
0000111  
0100000  
0111110  
0111000

 

이 배열에서는 총 세 개의 단지가 존재하며, 각 단지의 크기는 각각 7, 8, 9이다.

 

 

 

DFS를 활용한 탐색

깊이 우선 탐색(DFS)은 그래프나 2차원 배열 탐색에서 효율적으로 사용된다. 방향 벡터를 정의하여 오른쪽, 아래, 왼쪽, 위로 이동하며 1을 만나면 탐색을 진행한다. 방문한 노드는 0으로 변경하여 중복 방문을 방지한다.

탐색 과정은 다음과 같다.

1. 배열의 모든 위치를 순회하며 1을 찾는다.
2. 1을 발견하면 DFS를 호출하여 단지 탐색을 시작한다.
3. DFS를 통해 방문한 1의 개수를 세고, 이 값을 단지 크기로 반환한다.
4. 반환된 단지 크기를 리스트에 저장한다.

---

코드 구현

아래는 DFS를 활용해 단지 크기를 계산하는 코드이다.

 

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 배열의 크기
        int[][] aptList = new int[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            aptList[i] = stringToIntArray(line);
        }

        int[] dr = {0, 1, 0, -1}; // 오, 아, 왼, 위
        int[] dc = {1, 0, -1, 0}; // 오, 아, 왼, 위

        List<Integer> components = new ArrayList<>(); // 각 단지 크기 저장

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (aptList[i][j] == 1) { // 방문하지 않은 집(1) 발견 시
                    int cnt = dfs(aptList, i, j, dr, dc, N);
                    components.add(cnt); // 현재 단지 크기를 리스트에 추가
                }
            }
        }

        // 결과 출력
        Collections.sort(components);
        System.out.println(components.size()); // 단지 수
        components.forEach(System.out::println); // 각 단지의 크기
    }

    private static int dfs(int[][] aptList, int r, int c, int[] dr, int[] dc, int N) {
        aptList[r][c] = 0; // 방문 처리
        int cnt = 1; // 현재 노드 포함

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            // 범위를 벗어나지 않고, 아직 방문하지 않은(1) 경우
            if (nr >= 0 && nr < N && nc >= 0 && nc < N && aptList[nr][nc] == 1) {
                cnt += dfs(aptList, nr, nc, dr, dc, N); // 재귀 호출 후 개수 누적
            }
        }
        return cnt; // 총 방문한 노드 수 반환
    }

    private static int[] stringToIntArray(String line) {
        int[] result = new int[line.length()];
        for (int i = 0; i < line.length(); i++) {
            result[i] = line.charAt(i) - '0'; // 문자 → 숫자 변환
        }
        return result;
    }
}

 

 

주요 구현 사항

1. DFS 함수
   DFS는 탐색 과정에서 현재 노드의 값을 0으로 변경하여 방문 처리를 한다. 방문한 노드의 개수를 세기 위해 cnt를 1로 초기화하고, 4방향으로 탐색하며 방문 가능한 노드들을 재귀적으로 호출한다.
2. 방향 벡터 사용
   dr과 dc 배열을 사용해 오른쪽, 아래, 왼쪽, 위로 이동한다. 이를 통해 코드의 가독성을 높이고, 이동 방향을 쉽게 확장할 수 있다.
3. 단지 크기 저장
   모든 탐색이 끝난 뒤 각 단지의 크기를 리스트에 저장한다. 이를 통해 결과를 정리하고 출력할 수 있다.

 

마무리

DFS는 그래프 탐색 문제를 해결하는 데 매우 유용한 알고리즘이다. 방문 처리와 방향 벡터를 적절히 활용하면 간단한 코드로 효율적인 탐색을 구현할 수 있다. 2차원 배열에서 특정 영역을 탐색하거나 크기를 계산하는 문제를 해결할 때 기본적인 방법으로 사용할 수 있다.

이 과정을 통해 문제를 해결하는 로직을 명확히 이해하고, 코드의 재사용성을 높이는 설계를 할 수 있다.