[2667] 단지번호붙이기

🔗 문제 링크

https://www.acmicpc.net/problem/2667

🔍 문제 설명

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

⚠️ 제한사항

• $5 ≤ N ≤ 25$

---

🗝 풀이 (언어 : Java)

옛날에 풀어본 섬의 개수찾는 문제와 같은 문제이다. 이중 반복문으로 모든 지점을 체크하되, 이차원 배열을 이용하여 이미 체크한 아파트가 아닌 경우에만, 단지 개수를 찾는 함수를 실행한다. 개수를 카운트하고, 방문 체크를한 뒤에는 상하좌우로 인접한 위치에 아파트가 존재하는지 재귀호출로 찾는다. 범위가 넘어가거나, 이미 방문한 경우에는 스킵한다. 해당 영역의 단지 수를 찾았으면 오름차순으로 정렬하여 정답을 출력해준다. 마지막에 당황한 점은 BuffedWriter는 write함수의 인자로 숫자를 받을 수 없다. 하나하나 String으로 변환해서 넣어주어야 한다.

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

class Main {
    private List<Integer> answer = new ArrayList<>();
    private int count = 0;

    private void dfs(int x, int y, int n, String[][] matrix, boolean[][] visited) {
        // 범위를 넘거나, 이미 체크한 아파트, 아파트가 아니면 스킵
        if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || matrix[x][y].equals("0"))
            return;
        // 아파트 개수 카운트, 방문 체크하고 상하좌우로 연결된 아파트 찾기
        count++;
        visited[x][y] = true;
        dfs(x-1, y, n, matrix, visited);
        dfs(x+1, y, n, matrix, visited);
        dfs(x, y-1, n, matrix, visited);
        dfs(x, y+1, n, matrix, visited);
    }

    private void findComplex(int n, String[][] matrix) throws IOException {
        boolean[][] visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 이미 앞에서 단지에 포함된 아파트거나 아파트가 아니면 다음으로
                if (visited[i][j] || matrix[i][j].equals("0"))
                    continue;
                dfs(i, j, n, matrix, visited); // 단지 수 조회
                if (count > 0) // 단지를 찾으면 개수 정답 리스트에 넣기
                    answer.add(count);
                count = 0; // 단지수 초기화
            }
        }
        // 정답 문자열 만들고 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Collections.sort(answer); // 오름차순 정렬
        bw.write(String.valueOf(answer.size()));
        for (int num : answer) {
            bw.write("\n");
            bw.write(String.valueOf(num));
        }
        bw.flush();
        bw.close();
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] matrix = new String[n][n];
        for (int i = 0; i < n; i++)
            matrix[i] = br.readLine().split("");
        br.close();
        new Main().findComplex(n, matrix);
    }
}