๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 18์ผ์ฐจ TIL - ๋‹จ์ง€ ๋ฒˆํ˜ธ ๋ถ™์ด๊ธฐ

HOONSSACยท2024๋…„ 8์›” 8์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
18/41
post-thumbnail

โณ๋ฌธ์ œ

<๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์—ฐ๊ฒฐ๋˜์—ˆ๋‹ค๋Š” ๊ฒƒ์€ ์–ด๋–ค ์ง‘์ด ์ขŒ์šฐ, ํ˜น์€ ์•„๋ž˜์œ„๋กœ ๋‹ค๋ฅธ ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ๋งํ•œ๋‹ค. ๋Œ€๊ฐ์„ ์ƒ์— ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—ฐ๊ฒฐ๋œ ๊ฒƒ์ด ์•„๋‹ˆ๋‹ค. <๊ทธ๋ฆผ 2>๋Š” <๊ทธ๋ฆผ 1>์„ ๋‹จ์ง€๋ณ„๋กœ ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ธ ๊ฒƒ์ด๋‹ค. ์ง€๋„๋ฅผ ์ž…๋ ฅํ•˜์—ฌ ๋‹จ์ง€์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ฐ ๋‹จ์ง€์— ์†ํ•˜๋Š” ์ง‘์˜ ์ˆ˜๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ง€๋„์˜ ํฌ๊ธฐ N(์ •์‚ฌ๊ฐํ˜•์ด๋ฏ€๋กœ ๊ฐ€๋กœ์™€ ์„ธ๋กœ์˜ ํฌ๊ธฐ๋Š” ๊ฐ™์œผ๋ฉฐ 5โ‰คNโ‰ค25)์ด ์ž…๋ ฅ๋˜๊ณ , ๊ทธ ๋‹ค์Œ N์ค„์—๋Š” ๊ฐ๊ฐ N๊ฐœ์˜ ์ž๋ฃŒ(0ํ˜น์€ 1)๊ฐ€ ์ž…๋ ฅ๋œ๋‹ค.

์ถœ๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ด ๋‹จ์ง€์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜์‹œ์˜ค. ๊ทธ๋ฆฌ๊ณ  ๊ฐ ๋‹จ์ง€๋‚ด ์ง‘์˜ ์ˆ˜๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•˜์‹œ์˜ค.

์ž…์ถœ๋ ฅ ์˜ˆ

์˜ˆ์ œ ์ž…๋ ฅ 1

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

์˜ˆ์ œ ์ถœ๋ ฅ 1

3
7
8
9

โœ๏ธํ’€์ด

์ด ๋ฌธ์ œ๋Š” ์ธ์ ‘ํ•œ ํ–‰๋ ฌ์˜ ๊ฐ’์„ ํŒ๋‹จํ•˜์—ฌ ๊ณ„์† ํƒ์ƒ‰ํ•ด ๋‚˜๊ฐ€๋Š” ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์—, DFS๋‚˜ BFS๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ๋  ๊ฒƒ์ด๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.

๋‘˜ ์ค‘, ๋‚˜๋Š” DFS๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด ๋ณด์•˜๋‹ค.

๋‹จ์ง€๋ฅผ ํƒ์ƒ‰ํ•ด ๋‚˜๊ฐ€๋Š” ๊ณผ์ •์€
๋งŒ์•ฝ, ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ง‘์„ ๋ฐœ๊ฒฌํ–ˆ๋‹ค๋ฉด, ํ•ด๋‹น ์ง‘์˜ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํ•€ ํ›„,
์ธ์ ‘ํ•œ ์ง‘์ด ์žˆ๋‹ค๋ฉด, ํ•ด๋‹น ์ง‘์œผ๋กœ ๋ฐฉ๋ฌธ ํ›„ DFS๋ฅผ ํ˜ธ์ถœํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์„ค๊ณ„๋ฅผ ํ•˜์˜€๋‹ค.

์ฃผ์˜ํ•ด์•ผ ํ•  ์ ์€ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํ•„ ๋•Œ, ์ง€๋„ ๋ฒ”์œ„ ๋ฐ–์„ ํƒ์ƒ‰ํ•˜๋ฉด Out Of Bound ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํƒ์ƒ‰ํ•  ์ธ๋ฑ์Šค๊ฐ€ ์ง€๋„ ๋ฒ”์œ„ ์•ˆ์ด๋ผ๋Š” ์กฐ๊ฑด์„ ๊ณ ๋ คํ•ด์•ผ ํ•œ๋‹ค.

ํ˜„์žฌ ์ง‘์ด๋ž‘ ์ธ์ ‘ํ•˜๊ณ , ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ง‘์„ ๋ฐฉ๋ฌธํ•ด DFS ํ˜ธ์ถœ์„ ํ•  ๋•Œ, count๋ณ€์ˆ˜๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ ๋‹จ์ง€ ์ˆ˜๋ฅผ ์ฆ๊ฐ€์‹œ์ผœ ์ฃผ๊ณ , ๋‹จ์ง€ ํƒ์ƒ‰์ด ๋๋‚ฌ์„ ๋•Œ ์ด๋ฅผ ๋ฐ˜ํ™˜ํ•ด ๋ฐฐ์—ด์— ์ €์žฅํ•˜๋„๋ก ๊ตฌํ˜„ํ•˜์˜€๋‹ค.

๐Ÿ‘พ์ตœ์ข… ์ฝ”๋“œ

import java.util.ArrayList;
import java.util.Scanner;
import static java.util.Collections.sort;

public class Main {
    static int[][] map; // ์ง€๋„
    static boolean[][] visited; // ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ๋ฐฐ์—ด
    static int size; // ์ง€๋„์˜ ํฌ๊ธฐ
    static int count;
    static int[][] see = {{-1, 0},{1, 0}, {0, -1}, {0, 1}}; // ์ƒํ•˜์ขŒ์šฐ

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        size = sc.nextInt();
        sc.nextLine();
        map = new int[size][size]; // ์ง€๋„ ์ƒ์„ฑ
        visited = new boolean[size][size]; // ๋ฐฉ๋ฌธ ์—ฌ๋ถ€
        ArrayList<Integer> result = new ArrayList<>();

        // ๋ฐฐ์—ด ์ž…๋ ฅ๋ฐ›๊ธฐ
        for (int i = 0; i < size; i++) {
            String[] input = sc.nextLine().split("");
            for (int j = 0; j < size; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }

        // ๋‹จ์ง€ ์ฐพ๊ธฐ
        for (int i = 0; i < size; i++){
            for (int j = 0; j < size; j++) {
                // ์ง‘์ด ์กด์žฌํ•˜๊ณ  ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜์„ ๊ฒฝ์šฐ
                if (map[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    dfs(i, j); // dfs ํ˜ธ์ถœ
                    result.add(count); // ๋‹จ์ง€ ์ˆ˜ ์ €์žฅ
                }
            }
        }

        System.out.println(result.size());
        sort(result);
        for (int integer : result) {
            System.out.println(integer);
        }
    }

    // DFS
    static void dfs(int x, int y) {
        count++; // ๋‹จ์ง€ ์ˆ˜ ์ฆ๊ฐ€
        visited[x][y] = true;

        // ์ƒํ•˜์ขŒ์šฐ ํƒ์ƒ‰
        for (int i = 0; i < see.length; i++) {
            // ์ƒํ•˜์ขŒ์šฐ ์ด๋™ํ•œ ์ขŒํ‘œ
            int newX = x + see[i][0];
            int newY = y + see[i][1];

            // ์ด๋™ํ•œ ์ขŒํ‘œ๊ฐ€ map ์•ˆ์— ์žˆ๊ณ , ์ด๋™ํ•œ ์ขŒํ‘œ์— ์ง‘์ด ์žˆ๊ณ , ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์•˜์„ ๋•Œ
            if (newX >= 0 && newX < size && newY >= 0 && newY < size && map[newX][newY] == 1 && !visited[newX][newY]) {
                dfs(newX, newY);
            }
        }
    }
}

DFS๋ฅผ ๋ฌธ์ œ์— ์ ์šฉํ•˜๋Š” ๊ฒŒ ์•„์ง์€ ์–ด๋ ต๊ธด ํ•˜์ง€๋งŒ, ์œ ์‚ฌํ•œ ๋ฌธ์ œ๋ฅผ ๋” ํ’€์–ด๋ณด๋ฉฐ ์ ์‘์„ ํ•ด์•ผ๊ฒ ๋‹ค๐Ÿ˜‚


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

2๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 8์ผ

ํ•œ๊ณ„๋ฅผ ๋›ฐ์–ด๋„˜์–ด๐Ÿ”ฅ๐Ÿ”ฅ

1๊ฐœ์˜ ๋‹ต๊ธ€