[JAVA/2667번] 단지번호붙이기

문제

입력 및 출력

풀이

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

class Main {
    public static int N;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1, -1, 0, 0};
    public static int[][] map;
    public static boolean[][] visited;
    public static int count;
    public static ArrayList < Integer > list = new ArrayList < > ();
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 지도의 크기 N
        N = Integer.parseInt(br.readLine());

        // 지도
        map = new int[N][N];
        visited = new boolean[N][N];

        // 지도 데이터 입력
        for (int i = 0; i < N; i++) {
            String[] temp = br.readLine().split("");
            for (int j = 0; j < temp.length; j++) {
                map[i][j] = Integer.parseInt(temp[j]);
            }
        }

        // 지도 전체 탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    count = 0;
                    BFS(i, j);
                    list.add(count + 1);
                }
            }
        }

        // 총 단지 수 출력
        System.out.println(list.size());

        // 단지내 집 순 출력
        Collections.sort(list);
        for (int result: list) {
            System.out.println(result);
        }
    }
    public static void BFS(int x, int y) {
        // Node타입을 갖는 큐 선언
        Queue < Node > queue = new LinkedList < > ();

        queue.add(new Node(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            // 이동할 수 있는 방향은 총 4가지(상, 하, 좌, 우)
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                // 범위 안에 포함되고
                if (isRange(nx, ny)) {
                    if (map[nx][ny] == 1 && !visited[nx][ny]) {
                        queue.add(new Node(nx, ny));
                        visited[nx][ny] = true;
                        count++;
                    }
                }
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if (x >= 0 && y >= 0 && x < N && y < N) {
            return true;
        }
        return false;
    }
}

class Node {
    // x축, y축
    int x, y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법
이번 문제는 상, 하, 좌, 우로 붙어있는 집을 단지로 정의하고, 단지의 수와 단지 내 속한 집의 수를 출력하는 문제였다.

문제를 풀며, 가장 신경섰던 부분은 단지 내 속한 집의 수를 세는 부분이였다. 이중 반복문을 돌며 지도를 탐색하는데 해당 인덱스가 집이고, 방문되지 않았을 경우 BFS를 호출해준다.

이때 BFS를 호출해주기 전 count의 값을 0으로 초기화해주는 것이 중요하다. count는 전역에서 사용할 수 있는 변수이기 때문에 BFS메소드가 수행함에 따라 연결되있는 집이 있을 경우 1씩 증가하게 될 것이다. 단지의 수와 단지내 집의 수를 출력하기 위해 결과 값을 리스트에 넣고 정렬을 해주었다.