[알고리즘 PS] 백준 2667번 단지번호붙이기 자바 문제풀이

문제

해당 포스팅은 백준의 2667번 단지번호붙이기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이 문제는 전형적인 Connected Component 문제이다.

다른 말로는 연결 요소 찾기라고 하는데, 해당 문제보다 조금 쉬운 버전이 백준의 11724번 연결 요소의 개수 문제이다.

연결 요소의 개수 문제 풀이에서 해당 문제의 접근과 해결을 볼 수 있으니 참고하면 좋을 듯 하다.

 

하지만 지난 연결 요소의 개수 문제 풀이와 다른 점이라고 한다면, 인접 리스트가 아니라 이차원 행렬이 그래프가 된다는 것이다.

인접 리스트는 하나의 노드가 몇 개의 노드를 갖는지 확실하지 않고, 얼마나 깊은 Depth를 갖는지 확실하지 않을 때 자주 사용된다.

 

하지만 이런식으로 행렬이 노드가 되는 경우에는 하나의 노드는 최대 4개와 연결된다는 특징을 알고 있기 때문에 그대로 사용해도 무리가 없다.

 

그리고 이 문제 또한 연결 요소를 찾기 위해서 dfs 탐색을 이용하면 된다.

오답 후보

우선 기저 사례가 2개가 있어야 한다.

1. x, y가 범위를 넘어갈 경우
2. graph[x][y] == 0 즉 집이 아닌 경우

또 다른 오답 후보는, 문제에서 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.라고 나왔다.

 

결과를 출력할 때 정렬을 한 번 수행해야 한다.

정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    static int[][] graph;
    static int count;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());

        graph = new int[n][n];
        ArrayList<Integer> answer = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] house = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(house[j]);
            }
        }
        int called = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(dfs(i, j)) {
                    called++;
                    answer.add(count);
                    count = 0;
                }
            }
        }
        bw.write(called + "\n");
        Collections.sort(answer);
        for(int number: answer) bw.write(number + "\n");
        bw.flush();
        bw.close();
    }

    private static boolean dfs(int x, int y) {
        if(x < 0 || y < 0 || x > n-1 || y > n-1) return false;
        if(graph[x][y] == 0) return false;
        graph[x][y] = 0;
        count++;
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);

        return true;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.