[백준]2667번 단지번호붙이기 - Java

문제

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

2667번: 단지번호붙이기

 

풀이

요즘 DFS 문제를 많이 풀려고 함!

이 문제도 최근에 풀던 문제랑 비슷하다고 볼 수 있겠음

 

내 생각에 포인트는

DFS로 단지가 몇개인지 판단한 후 단지에 번호를 어떻게 붙이고 어떻게 해당 단지에 속하는 아파트의 개수를 세느냐! 인 것 같음

나는 해당 단지에 속하는 아파트의 개수를 세는 함수를 따로 만들었고 그 함수 안에서 새로 배열을 만들고 그 배열의 인덱스를 증가시켜 정렬한 후 반환해줬음!

 

자세한건 주석으로!

 

코드

// 2667번 단지번호붙이기
// https://www.acmicpc.net/problem/2667

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Num2667_단지번호붙이기 {
    static int[][] map;
    static boolean[][] visited;
    static int N;
    static int AptCount = 0; // 단지 수
    // 사방 탐색(우하좌상)
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

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

        map = new int[N][N];
        visited = new boolean[N][N];

        // 입력
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    solution(i, j);
                    AptCount++;
                }
            }
        }

        int[] answerArr = answerCount();

        // 출력
        StringBuilder sb = new StringBuilder();
        sb.append(AptCount).append("\n");
        for (int i = 0; i < answerArr.length; i++) {
            sb.append(answerArr[i]).append("\n");
        }
        sb.setLength(sb.length() - 1);

        System.out.println(sb);
    }

    // DFS: map에 몇개의 단지가 있는지 판단하는 함수
    private static void solution(int i, int j) {
        if (visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        map[i][j] = AptCount + 1;

        for (int k = 0; k < 4; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];

            if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                continue;
            }

            if (map[nr][nc] == 1 && !visited[nr][nc]) {
                solution(nr, nc);
            }
        }
    }

    // 정답 배열을 반환하는 함수
    private static int[] answerCount() {
        // 단지 수만큼의 크기를 가진 배열을 만들어줌
        int[] tempArr = new int[AptCount];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] > 0) {
                    // 인덱스가 같으면 같은 단지이므로 해당 단지에 포함되는 아파트면 더해줌
                    tempArr[map[i][j] - 1]++; // 쉽게 말해서 한 단지에 몇개의 아파트가 있는지 세는거임
                }
            }
        }

        Arrays.sort(tempArr); // 오름차순 정렬
        
        return tempArr;
    }
}