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

2667 단지번호붙이기

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

문제설명

정사각형 모양의 지도에서 단지를 탐색하고, 각 단지의 집 수를 오름차순으로 정렬

접근방식

 

DFS가 방문하는 모든 집을 정확히 한 번씩 방문하므로, 탐색 시간은 모든 집을 한번씩 방문하는 시간인 O(N2)이다.

정렬 작업은 O(Mlog⁡M)의 시간 복잡도를 가지며, 여기서 M은 단지의 수이다.

단지의 수는 O(N2)이기 때문에 O(N2logN2) 시간 복잡도를 가진다.

 

 

문제 조건 분석 과정

 

정사각형 모양의 지도가 주어진다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

각 단지의 집 수를 오름차순으로 정렬하여 출력한다. 단지의 수와 각 단지의 집 수를 출력한다.

 

 

전체코드

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

public class Main {
    private static final int[] dx = {-1, 1, 0, 0}; // 상 하
    private static final int[] dy = {0, 0, -1, 1}; // 좌 우

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //지도 크기

        int[][] map = new int[N][N]; //지도
        boolean[][] visited = new boolean[N][N]; //방문 여부

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

        //단지의 크기
        List<Integer> complexSizes = new ArrayList<>();

        //전체 지도를 순회하며 단지 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //집이 있고, 아직 방문하지 않은 경우
                if (map[i][j] == 1 && !visited[i][j]) {
                    //DFS를 통해 단지 탐색, 크기 계산
                    complexSizes.add(dfs(i, j, N, map, visited));
                }
            }
        }

        //단지 크기 리스트 = 오름차순
        Collections.sort(complexSizes);

        //총 단지 수
        System.out.println(complexSizes.size());

        //각 단지의 집 수
        for (int size : complexSizes) {
            System.out.println(size);
        }
    }

    private static int dfs(int x, int y, int N, int[][] map, boolean[][] visited) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {x, y}); //시작 집
        visited[x][y] = true; //시작 집 방문
        int count = 0; //단지 내 집의 수

        while (!stack.isEmpty()) {
            int[] cell = stack.pop(); //스택에서 집을 꺼냄
            int cx = cell[0];
            int cy = cell[1];
            count++; //집의 수 증가

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i]; //상 하
                int ny = cy + dy[i]; //좌 우

                //다음 집의 좌표가 유효하고, 집이 있으며, 방문하지 않았을 경우
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && map[nx][ny] == 1) {
                    visited[nx][ny] = true; //방문 표시
                    stack.push(new int[] {nx, ny}); //스택에 추가
                }
            }
        }

        return count; //단지 내 집의 수
    }
}