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

💡문제 분석 요약

주어진 지도 정보를 통해 연결된 집들의 단지를 찾아 단지 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• `int[n][n] house` 에 지도 정보를 저장한다.
• `house` 의 모든 위치를 반복
  • 집이 존재하고 방문하지 않은 경우 (`house[i][j] == 1 && !visited[i][j]`)
    • 단지 수(`count`)를 1 증가시키고, 단지 내 집의 수(`house_count`)를 1로 초기화한다.
    • 해당 위치을 방문 처리한다. (`visited[i][j] = true`)
    • dfs 함수를 호출해 해당 위치의 상하좌우 집을 검사한다.
    • `house_counts`에 현재 단지내 집의 수를 추가한다.
• dfs 함수
  • 현재 집의 상하좌우를 검사한다.
  • 검사하는 집이 존재하고, 방문하지 않은 경우
    • 해당 위치를 방문 처리(`visited`)하고, 단지 내 집의 수(`house_count`)를 1 증가시킨다.
    • 해당 집의 상하좌우를 검사한다. (재귀 호출)
• `house_counts`를 오름차순 정렬한다.

 

💡코드

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

public class Main {
    static int n;
    static int[][] house;
    static boolean[][] visited;
    static int count = 0;
    static int house_count = 0;

    static void dfs(int i, int j) {
        int[] dx = {-1, 1, 0, 0}; // 상하좌우 행 이동
        int[] dy = {0, 0, -1, 1}; // 상하좌우 열 이동

        for(int k=0; k<4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];

            if(x >= 0 && x < n && y >= 0 && y < n && house[x][y] == 1 && !visited[x][y]) {
                visited[x][y] = true;
                house_count++;
                dfs(x, y);
            }
        }
    }

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

        n = Integer.parseInt(br.readLine());
        house = new int[n][n];
        for(int i=0; i<n; i++) {
            String str = br.readLine();
            for(int j=0; j<n; j++) {
                house[i][j] = str.charAt(j) - '0';
            }
        }

        visited = new boolean[n][n];
        ArrayList<Integer> house_counts = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(house[i][j] == 1 && !visited[i][j]) {
                    count++;
                    house_count = 1;
                    visited[i][j] = true;
                    dfs(i, j); // 상하좌우 검사
                    house_counts.add(house_count);
                }
            }
        }

        // 단지내 집의 수 오름차순 정렬
        Collections.sort(house_counts);
        System.out.println(count);
        for(int house_count : house_counts) {
            System.out.println(house_count);
        }
    }
}

 

💡시간복잡도

$O(N^2)$

 

💡 틀린 이유

`house_counts` 를 오름차순 정렬하지 않았다.

 

💡 다른 풀이

기존에는 if문을 4개 사용해 해당 위치의 상하좌우를 검사하도록 했다. 다른 풀이를 찾아보니 이 코드를 방향 배열을 사용해 더 간결하게 구현할 수 있었다.

기존 코드

static void dfs(int i, int j) {
    if(i-1 >= 0 && house[i-1][j] == 1 && !visited[i-1][j]) {
        visited[i-1][j] = true;
        house_count++;
        dfs(i-1, j);
    }
    if(i+1 < n && house[i+1][j] == 1 && !visited[i+1][j]) {
        visited[i+1][j] = true;
        house_count++;
        dfs(i+1, j);
    }
    if(j-1 >= 0 && house[i][j-1] == 1 && !visited[i][j-1]) {
        visited[i][j-1] = true;
        house_count++;
        dfs(i, j-1);
    }
    if(j+1 < n && house[i][j+1] == 1 && !visited[i][j+1]) {
        visited[i][j+1] = true;
        house_count++;
        dfs(i, j+1);
    }
}

 

수정한 코드

static void dfs(int i, int j) {
    int[] dx = {-1, 1, 0, 0}; // 상하좌우 행 이동
    int[] dy = {0, 0, -1, 1}; // 상하좌우 열 이동

    for(int k=0; k<4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];

        if(x >= 0 && x < n && y >= 0 && y < n && house[x][y] == 1 && !visited[x][y]) {
            visited[x][y] = true;
            house_count++;
            dfs(x, y);
        }
    }
}

`dx` 와 `dy` 배열을 사용해 상하좌우 이동을 표현할 수 있다.

 

💡 느낀점 or 기억할정보

오름차순 정렬하는 메서드를 기억하자!