단지번호붙이기

문제 정보

• 사이트 : 백준 알고리즘 사이트
• 문제 번호 : 2667
• 문제 분류 : dfs
• 난이도 : silver 1

문제 풀이

내가 짠 코드

생각한 문제 조건
1. 1) 총 단지수와 2) 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력
2. 지도의 크기 N (5<=N<=25)
3. 지도 값 1 = 집 0 = 집 X(벽)
4. 최대 최소 데이터 생각하기

• N = 5일 때 : 딱히 예외 사항 X
• N = 25일 때 : map을 인접행렬로 구현해도 무리없음
• 총 단지수가 가장 작을 때 = 단지 내 집의 수 가장 클 때
  • 모든 map이 1일때
    • 단지수 1
    • 단지에 속하는 집의 수 (N^2 = 625)
• 총 단지수가 가장 클 때 = 단지 내 집의 수 가장 작을 때
  • 격자 형태일 때
    • 단지의 속하는 집의 수 1
    • 단지의 수 (N^2 / 2 = 약 312)
• DFS의 시간 복잡도 = O(V+E)
  • 정점의 최대 : O(N^2)
  • 간선의 최대 : O(N^2 * 4)
  • O(V+E) = O(N^2 + 4N^2) = O(N^2)
  • N 최대가 25이므로 DFS 사용 가능 (제한 1초, 625<1억)

💭 생각 노트

• N이 5이상 25이하이므로 인접행렬로 구현하여도 성능이 괜찮을 것 같다.
• map을 돌다가 방문하지 않고 map[i][j]==1이면 dfs를 실행한다.
• 이때 단지 내의 집의 수를 세야하므로 dfs들어가기 전 count = 0으로 초기화 시켜주고 단지 수를 증가시킨다.
• 출력은 단지내 수를 오름차순으로 정렬하여야하므로 출력하기 전 Collections.sort로 결과를 정렬시켜준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    private static int n, count, area = 0;
    private static int[][] map;
    private static boolean[][] visit;
    private static final int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static List<Integer> result = new ArrayList<>();

    public static void dfs(int x, int y) {
        count++;
        for (int i = 0; i < 4; i++) {
            int dx = x + check[i][0];
            int dy = y + check[i][1];
            if (0 <= dx && dx < n && 0 <= dy && dy < n) {
                if (!visit[dx][dy] && map[dx][dy] == 1) {
                    visit[dx][dy] = true;
                    dfs(dx, dy);
                }
            }
        }
    }

    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];
        visit = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && map[i][j] == 1) {
                    count = 0;
                    visit[i][j] = true;
                    area++;
                    dfs(i, j);
                    result.add(count);
                }
            }
        }
        Collections.sort(result);

        System.out.println(area);
        for (Integer integer : result) {
            System.out.println(integer);
        }
        br.close();
    }
}

문제 출처

• 단지번호붙이기

썸네일 출처

Image by storyset on Freepik