Midnight Coder's Lounge

[백준][JAVA] 2667 - 단지번호붙이기 (11612KB, 64ms, Java 8) 본문

Algorithm

[백준][JAVA] 2667 - 단지번호붙이기 (11612KB, 64ms, Java 8)

AtomicLiquors 2024. 12. 24. 18:54

 

실버1 티어 DFS 문제인 단지번호붙이기 문제 풀이입니다.
제법 많은 분들께서 제 문제 풀이를 조회해 주셔서, 블로그에 직접 문제 해설을 올리기로 마음먹었습니다.

 

 

 

 

* 선수지식 : DFS, PriorityQueue



 문제 링크 

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

 

 


 개요 

 

"이차원 평면 위에 1로 표현된 '집'들을 상하좌우로 연결한 묶음을 '단지'라고 하겠습니다.
 첫째 줄에 총 단지 수가 몇 개인지 출력해 주세요.
 그 후 단지별로 들어 있는 집의 수를 오름차순 정렬해서 한 줄씩 출력해 주세요."

 

 

 코드 

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

public class Main {
    static int N;
    static boolean[][] map;
    static int[] dR = {0, 0, -1, 1};
    static int[] dC = {-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());
        map = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = (input.charAt(j) == '1');
            }
        }

        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if(map[r][c]){
                    answer++;
                    pq.offer(dfs(r, c));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(residence).append('\n');
        while(!pq.isEmpty()){
            sb.append(pq.poll()).append('\n');
        }
        System.out.print(sb);
    }

    static int dfs(int r, int c){
        map[r][c] = false;
        int nr, nc;
        int houses = 1;
        for (int dir = 0; dir < 4; dir++) {
            nr = r + dR[dir];
            nc = c + dC[dir];
            if(isInBound(nr, nc)){
                houses += dfs(nr, nc);
            }
        }
        return houses;
    }

    static boolean isInBound(int r, int c){
        return r >= 0 && c >= 0 && r < N && c < N && map[r][c];
    }
}

 

 

 

 해설  

📌이차원 배열 초기화 : boolean[][] 타입 사용

표현하려는 값이 0과 1밖에 없어서  int[][] 보다 메모리를 적게 사용하는  boolean[][] 을 사용해도 충분합니다.

입력 1로 주어지는 '집'은  true 로, 입력 0으로 주어지는 빈 공간은  false 로 치환합니다.

참고로 이 이차원 배열은 집의 위치를 나타낼 뿐만 아니라 방문 체크 역할까지 겸할 예정입니다.

 map = new boolean[N][N];

for (int i = 0; i < N; i++) {
    String input = br.readLine();
    for (int j = 0; j < N; j++) {
    // 입력을 받아서 값이 1이면 true, 0이면 false를 대입합니다.
        map[i][j] = (input.charAt(j) == '1');
    }
}

 

 

📌dfs 탐색

집을 발견할 때마다 dfs로 탐색하려 합니다.

이 때 집이 총 몇 개인지 갯수를 세기 위해 dfs 함수가 집의 갯수를 저장한  int 값을 반환하도록 만듭니다.

 

또한 앞서 말씀드린 것처럼 map[][]dfs 중복 탐색을 방지하기 위해 방문 여부를 체크하는 용도로도 사용하겠습니다.
추후 집의 위치 정보를 다시 사용할 필요가 없기 때문에, 굳이 2차원 배열을 새로 선언해서 메모리를 추가로 사용하는 게 아니라
기존의 map[][]의 값을 곧바로  false 로 바꿔버릴 것입니다.

static int dfs(int r, int c){
    // 현재 위치의 map값을 false로 바꿔 중복 방문을 방지합니다.
    map[r][c] = false;
    int nr, nc;
    
    // 단지 안에 속한 집의 총 갯수를 저장할 int 변수입니다. 현재 위치에 집이 하나 있었으니 1로 초기화합니다.
    int houses = 1;
    
    for (int dir = 0; dir < 4; dir++) {
    //	4방 델타 탐색
        nr = r + dR[dir];
        nc = c + dC[dir];
        if(isInBound(nr, nc)){
        	// 집이 존재하는 좌표에 대해 dfs 탐색을 재귀적으로 실행합니다.
            // 각각의 탐색 결과 집이 총 몇 개였는지 houses에 저장하겠습니다.
            houses += dfs(nr, nc);
        }
    }
    
    // houses의 총합을 결과값으로 반환하고 탐색을 종료합니다.
    return houses;
}


static boolean isInBound(int r, int c){
    return r >= 0 && c >= 0 && r < N && c < N && map[r][c];
}

 

 

 

📌PriorityQueue를 사용한 정답 값의 오름차순 정렬

방문하지 않은 집을 발견할 때마다 단지 수를 증가시키고, dfs 결과를 PQ에 저장합니다.

PQ에 저장된 정수 값들은 자동으로 오름차순 정렬되어서 저장될 것입니다.

// 단지의 갯수를 저장할 int변수, 단지별 집의 갯수를 정렬해서 저장할 PQ입니다.
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
        if(map[r][c]){
        // 아직 방문하지 않은 집을 발견할 때마다 단지 갯수를 1 증가시킵니다.
            answer++;
            // 그 후 dfs 탐색을 실행하고, 결괏값을 즉시 PQ에 저장합니다.
            pq.offer(dfs(r, c));
        }
    }
}

StringBuilder sb = new StringBuilder();

// 단지의 갯수를 StringBuilder에 저장합니다.
sb.append(answer).append('\n');

while(!pq.isEmpty()){
	// PQ에서 오름차순으로 정렬된 단지별 집의 갯수를 순서대로 뽑아내, StringBuilder에 저장합니다.
    sb.append(pq.poll()).append('\n');
}

// StringBuilder를 출력합니다.
System.out.print(sb);

 

 

 

 

 제출 결과  

 

 

 


 

 

 

보통 백준에서 문제 하나를 풀 때마다 한 분 정도 찾아와서 조회해 주시는데,

이번 문제 풀이는 4달 동안 30명 가까운 분들이 조회해 주셨습니다.

많은 분들께 참고가 된 것 같아 이렇게 직접 해설을 올리게 되었습니다.

 

 

코드와 관련된 피드백이나 질문이 있으시면 댓글 부탁드립니다.

Comments