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

[CMSSKKK]

TITLE

단지번호붙이기

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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


public class Main {

    private static int n;
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {1, -1, 0, 0};
    private static char[][] board;
    private static boolean[][] visit;
    private static int count = 0;
    private static int[] apart;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new char[n][n];
        visit = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                board[i][j] = line.charAt(j);
            }
        }
        apart = new int[n * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!visit[i][j] && board[i][j] == '1') {
                    dfs(i, j);
                    count++;
                }
            }
        }

        System.out.println(count);
        Arrays.sort(apart);
        for (int i = 0; i < apart.length; i++) {
            if (apart[i] != 0) {
                System.out.println(apart[i]);
            }
        }
    }

    private static void dfs(int x, int y) {

        visit[x][y] = true;
        apart[count]++;

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

            if(nx < 0 || ny < 0 || nx >= n || ny >= n) {
                continue;
            }

            if(!visit[nx][ny] && board[nx][ny] == '1') {
                dfs(nx, ny);
            }
        }
    }
}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )

[Seokho-Ham]

풀이 언어

-java

코드

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

public class BOJ2667 {

    private static int n;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    private static int[][] map;
    private static boolean[][] visited;

    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[] tokens = br.readLine().split("");

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(tokens[j]);
                if (map[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }

        int total = 0;
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    int count = bfs(i, j);
                    total++;
                    list.add(count);
                }
            }
        }

        System.out.println(total);
        Collections.sort(list);
        list.forEach(System.out::println);

    }

    public static int bfs(int x, int y) {
        int house = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while (!queue.isEmpty()) {
            house++;
            int[] cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    continue;
                }

                if (map[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx, ny});
                }
            }
        }

        return house;
    }
}

핵심 로직 혹은 자료구조

• bfs

시간 복잡도

• O( )