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

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

---

문제

---

풀이

[BFS]

import java.io.*;
import java.util.*;
public class Main {
    static int[][] arr;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int n, totalHouse;
    static PriorityQueue<Integer> count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        arr = new int[n][n];
        visited = new boolean[n][n];
        count = new PriorityQueue<>();

        for(int i = 0; i < n; i++){
            String row = br.readLine();
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(row.substring(j, j+1));
            }
        }


        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == 1 && !visited[i][j]){
                    Bfs(i, j);
                    count.offer(totalHouse);
                    totalHouse = 0;
                }
            }
        }

        System.out.println(count.size());
        while(!count.isEmpty()){
            System.out.println(count.poll());
        }

    }

    public static void Bfs(int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        totalHouse++;
        while(!queue.isEmpty()){
            int now[] = queue.poll();
            visited[i][j] = true;
            for(int k = 0; k < 4; k++){
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >= 0 && x < n && y < n){
                    if(arr[x][y] == 1 && !visited[x][y]){
                        visited[x][y] = true;
                        queue.offer(new int[] {x , y});
                        totalHouse++;
                    }
                }
            }
        }
    }
}

 

문장의 띄어쓰기 없이 조건식이 들어오기 때문에 한 줄 전체를 받아 substring로 배열의 값을 저장해 준다.

 

이후 모든 방문 배열을 검사하며 방문 배열이 체크되지 않은 경우에만 bfs를 시작하게 된다.

 

bfs가 시작되면 처음 들어온 집에 대해 totalHouse++ 를 해주고 이후 집이 확인될 때마다 ++를 해준다. 최종적으로 확인이 마무리되면 이를 우선순위 큐에 더해주고 totalHouse를 0으로 초기화한다. 우선순위 큐에 추가하는 이유는 답을 오름차순으로 출력해야 되기 때문에 값을 추가함과 동시에 오름차순으로 정렬시키기 위해서이다.

 

마지막으로 우선순위 큐의 사이즈를 출력해 단지 수를 파악하고 정렬된 값을 이용해 가구 수 오름차순 출력을 마무리한다.

 

[DFS]

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

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n][n];

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



        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(!visited[i][j] && arr[i][j] == 1) {
                    count = 0;
                    dfs(i,j);
                    list.add(count);
                }
            }
        }

        System.out.println(list.size());
        list.sort(null);
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

    }

    public static void dfs(int x, int y) {
        count++;
        visited[x][y] = true;
        
        for(int i = 0; i < 4; i++){
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if(nowX < n && nowX >= 0 && nowY < n && nowY >= 0 && !visited[nowX][nowY] && arr[nowX][nowY] == 1) {

                dfs(nowX, nowY);
            }
        }
    }
}

 

우선순위 큐를 사용하지않고 그냥 list.sort(null)를 사용했다. Collections.sort(list)를 사용해도 되나 null을 넣는 것이 처음이라 한번 사용해봤다.

 

마찬가지로 직접 사방탐색을하며 체크하는 방식이다.

 

BFS도 그렇고 DFS도 그렇고 visited배열을 사용하였다. 다만 다른 분들의 풀이를 봐보니 그냥 조건 식에 들어오는 순간 arr의 값을 0으로 수정하는 분도 있었다. 메모리 크기를 따지면 이 방법이 훨씬 유용하고 좋을 것 같다고 생각한다.