[백준2667] - 단지 번호 붙이기 (JAVA)

[문제]

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

2667번: 단지번호붙이기

 

---

 

[문제풀이 전]

 

처음 문제 풀때 생각없이 방문처리를 boolean 으로 하려해서 낭패를 보았다. 문제에 그림2를 보면 힌트가 주어졌다. 새로운 BFS가 시작되면 단지번호를 증가하여 결국 그림2 처럼 만들어 해당 개수만 세어주면 되는데 문제를 천천히 꼼꼼히 읽어야 겠다.. 

---

 

[문제풀이] 

 

BFS를 활용한 문제로  상하좌위 연결된 집의 모임을 단지라고 지정을 하여 번호를 붙여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하면 된다. 기본적인 BFS 인데 추가로 방문처리를 단지 번호로 할 것이다. 그 후 방문처리가 된 지도의 단지에 속하는 집의 수를 구해야하는데 2중 for문을 돌며 0이 아닌 해당 단지번호가 나왔을때  카운팅 정렬 처럼, 1차원 배열을 활용하여 카운팅을 할 여 정렬 후 출력하면 답을 구할 수 있다.

 

 

---

[소스코드] 

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

class Main {
    static class Node{
        int x;
        int y;

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

    static final int dx[] = {0, 0, 1, -1};
    static final int dy[] = {1, -1, 0, 0};
    static int n, cnt;
    static int[][] house;
    static int[][] dange;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        house = new int[n][n];
        dange = new int[n][n];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < n; j++) {
                house[i][j] = s.charAt(j) - '0';
            }
        }

        cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (house[i][j] == 1 && dange[i][j] == 0) {
                    cnt++;
                    bfs(i, j);
                }
            }
        }

        int[] ans = new int[cnt]; //단지번호의 수 만큼 배열 생성

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(dange[i][j] != 0){
                    ans[dange[i][j] - 1]++; //배열은 0,1,2 이기때문에 -1을 함.
                }
            }
        }

        Arrays.sort(ans);

        System.out.println(cnt);
        for (int i : ans) {
            System.out.println(i);
        }
        
    }

    static void bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x, y));
        dange[x][y] = cnt;

        while (!q.isEmpty()) {
            Node p = q.poll();
            x = p.x;
            y = p.y;

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

                 if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                     if (house[nx][ny] == 1 && dange[nx][ny] == 0) {
                         q.add(new Node(nx, ny));
                         dange[nx][ny] = cnt;
                    }
                }
            }

        }
    }
}