ํ‹ฐ์Šคํ† ๋ฆฌ ๋ทฐ

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

 

2667๋ฒˆ: ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ

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

www.acmicpc.net

 

์ดํ•ด

  • ํ•ด๋‹น ๋ฌธ์ œ๋Š” 2์ฐจ์› ๋ฐฐ์—ด๋กœ ์ฃผ์–ด์ง€๋Š” map์„ ํƒ์ƒ‰ํ•˜์—ฌ ์—ฐ๊ฒฐ๋œ ์ง€์—ญ์„ ์ฐพ๋Š” ๋ฌธ์ œ์ด๋‹ค.
  • ์ฆ‰ map์„ ์ˆœํšŒํ•˜๋ฉฐ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ๊ฐ€ ์žˆ๋‹ค๋ฉด ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ธ์ ‘ํ•œ ์ขŒํ‘œ๋ฅผ ๋ชจ๋‘ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•œ๋‹ค.
  • ์ด๋ ‡๊ฒŒํ•˜๋ฉด ์—ฐ๊ฒฐ๋œ ์ง€์—ญ์€ ๋ชจ๋‘ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋  ๊ฒƒ์ด๊ณ  map์„ ์ˆœํšŒ ์ค‘์— ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ๋ฅผ ์ฐพ๋Š”๋‹ค๋ฉด ์ƒˆ๋กœ์šด ์ง€์—ญ์˜ ๋ฐœ๊ฒฌ์„ ์˜๋ฏธํ•œ๋‹ค.
  • ๋”ฐ๋ผ์„œ map์„ ์ˆœํšŒํ•˜๋ฉฐ ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ๋ฅผ ์ฐพ์„ ์‹œ ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ์‹œ์ž‘์œผ๋กœ ์ฃผ๋ณ€์„ ํƒ์ƒ‰ํ•˜๊ณ , ์ฃผ๋ณ€์˜ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ์˜ ์ˆ˜๋ฅผ ๊ธฐ๋กํ•˜๋ฉด ๋œ๋‹ค.

 

 

 

ํ’€์ด

  • map์„ ์ˆœํšŒํ•˜๋ฉฐ ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ๋ฅผ ์ฐพ์„ ์‹œ ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ์‹œ์ž‘์œผ๋กœ ์ฃผ๋ณ€์„ ํƒ์ƒ‰ํ•œ๋‹ค.
  • ์ฃผ๋ณ€์„ ํƒ์ƒ‰ํ•˜๋ฉฐ, ๋ฐฉ๋ฌธ๋˜์ง€ ์•Š์€ ์ขŒํ‘œ์ธ ๊ฒฝ์šฐ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•˜๊ณ , ๊ฐœ์ˆ˜๋ฅผ 1 count ํ•œ๋‹ค. (outBound ์˜ˆ์™ธ์— ์ฃผ์˜ํ•˜์ž)
  • ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ํƒ์ƒ‰ํ•˜๋ฉฐ, ํƒ์ƒ‰ ์ข…๋ฃŒ ์‹œ ํ•ด๋‹น ํƒ์ƒ‰์—์„œ ๋ฐœ๊ฒฌํ•œ ์ง‘ ์ˆ˜๋ฅผ ๊ธฐ๋กํ•œ๋‹ค.
  • ์—ฌ๊ธฐ์„œ๋Š” ์šฐ์„ ์ˆœ์œ„ ํ์— ํ•ด๋‹น ๊ตฌ์—ญ์˜ ์ง‘ ์ˆ˜๋ฅผ ๊ธฐ๋กํ•ด์„œ ์ •๋‹ต์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

์ฝ”๋“œ

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

public class ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ_2667 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        StringBuilder resultStringBuilder = new StringBuilder();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        map = new int[N][N];

        for (int y = 0; y < N; y++) {
            String[] split = br.readLine().split("");
            for (int x = 0; x < split.length; x++) {
                map[y][x] = Integer.parseInt(split[x]);
            }
        }

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (map[y][x] == 1) {
                    priorityQueue.add(bfs(x, y));
                }
            }
        }


        resultStringBuilder.append(priorityQueue.size() + "\n");

        while (!priorityQueue.isEmpty()) {
            resultStringBuilder.append(priorityQueue.poll() + "\n");
        }


        bw.write(resultStringBuilder.toString());

        bw.close();
        br.close();
    }


    static int bfs(int x, int y) {
        boolean isOutBound = x < 0 || y < 0 || x >= N || y >= N;
        if (isOutBound) {
            return 0;
        }

        boolean isVisited = map[y][x] == 0;
        if (isVisited) {
            return 0;
        }

        map[y][x] = 0;

        return 1 + bfs(x + 1, y) + bfs(x - 1, y) + bfs(x, y + 1) + bfs(x, y - 1);
    }
}
๋ฐ˜์‘ํ˜•