[백준] 2667 : 단지번호붙이기 - java [자바]

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

2667번: 단지번호붙이기

 

이해

• 해당 문제는 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);
    }
}