[백준 JAVA 문제풀이] 알고리즘(너비 우선 탐색)- 2667번 단지번호 붙이기

알고리즘 - [너비 우선 탐색] - 2667번 단지번호 붙이기

문제

---

문제링크

 

풀이

---

아파트 단지마다 0으로 구분되어 있기 때문에, 한 단지를 탐색하고 나서 다른 단지를 탐색할 때 어떻게 해야 할지 고민을 많이 했다. 이중for문을 되도록이면 돌리고 싶지 않았지만, 이 방법밖에 없었던 것 같다. 그래도 if문을 통해 해당 좌표가 1이고 방문을 하지 않았을 경우에만 bfs를 돌렸기 때문에 시간이 그리 많이 낭비되지는 않았다. 결론적으로는 아직 방문하지 않은 1인 곳에서부터 bfs를 시작하며, 하나의 단지 탐색이 모두 끝나면 아직 방문하지 않은 단지를 찾아 bfs를 도는 구조이다. 단지를 탐색하면서 그 단지 안에 몇 개의 집이 있는지 카운트하고 그걸 result라는 리스트 원소로 추가해주었다.

bfs함수에서는 큐를 이용하였다. 현재 위치를 기준으로 상하좌우로 움직이며 방문할 좌표를 큐에 넣고, 큐가 완전히 빌 때까지 큐에서 하나씩 꺼내서 세는 구조이다. 집의 수를 각각 세도 되는데, 나는 집마다 몇 번째 동인지 지정해주고 싶어서 Pos라는 클래스에 행, 열, 동 번호까지 포함시켰다.

main함수에서 마지막에 Collections.sort 함수를 통해 ArrayList를 오름차순 정렬해주었고, '아파트 단지 수 = result 리스트의 크기' 이기 때문에 이를 먼저 출력하고, for문을 통해 리스트 안에 있는 원소를 차례대로 출력했다.

 

CODE

import java.util.*;

public class Main {
    static int n;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Pos> queue;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static ArrayList<Integer> result; // 단지 집의 수를 저장할 배열

    static class Pos {
        int row, col, num;
        public Pos(int row, int col, int num) {
            this.row = row;
            this.col = col;
            this.num = num; // 단지 집의 수 세기(동 번호)
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 지도의 크기
        map = new int[n][n]; // 2차원 배열
        visited = new boolean[n][n]; // 방문 여부 체크
        result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < n; j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j])
                    bfs(new Pos(i, j, 1));
            }
        }

        Collections.sort(result);
        System.out.println(result.size());
        for (int c : result)
            System.out.println(c);
    }

    public static void bfs(Pos pos1) {
        queue = new LinkedList<>();
        queue.add(pos1);
        visited[pos1.row][pos1.col] = true;
        int count = 0; // 초기화
        int dong = 1;
        while (!queue.isEmpty()) {
            Pos pos = queue.poll();
//            System.out.println(pos.row + ", " + pos.col + ", " + pos.num); // test
            for (int i = 0; i < 4; i++) {
                int nr = pos.row + dr[i];
                int nc = pos.col + dc[i];

                if (nr >= 0 && nc >= 0 && nr < n && nc < n) {
                    if (map[nr][nc] == 1 && !visited[nr][nc]) {
                        queue.add(new Pos(nr, nc, ++dong));
                        visited[nr][nc] = true;
                    }
                }
            }
            count = pos.num;
        }
        result.add(count);
    }
}

 

결과

---

DFS보다 코드는 길지만 재귀함수가 없어서 그런지 메모리와 시간은 더 적게 나오는 것을 확인할 수 있었다!