[알고리즘] 백준 2667번 단지번호붙이기 ( BFS )

백준 2667번 단지번호붙이기

문제 바로가기

---

오늘은 단지번호붙이기 문제를 풀어보았다.

원래 그림이나 이차원배열이 나오는 문제는 보기만해도 풀기 싫어서 넘기곤 했는데, BFS, DFS를 연습하면서 이제 그나마 거부감이 많이 줄었다.

문제는 2차원배열내에서 서로 이어진 단지가 몇개 있는지 찾는 문제로, 이와 비슷한 문제를 이전에 풀어본 경험이 있어서 쉽게 풀 수 있었다.

먼저 2차원배열을 잘 입력받아서 map이라는 배열에 넣어줬고, visited라는 2차원 boolean배열을 만들어 주었다.

이 후, 1이 있는 위치를 돌면서 bfs 함수에 넣어준다. 이 때 visited 값이 true이면 이미 다른 이어진 부분에서 체크를 했다는 뜻이므로 bfs함수를 돌지 않는다.

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

bfs함수 내부에서는 Queue를 만들어서 상, 하, 좌, 우를 탐색하여 visited값과 map값을 확인하여 서로 연결된 단지들을 찾아준다. 이때 count를 세어준다.

이 후 Queue가 비었을 때 static으로 선언해놓은 answer라는 ArrayList에 값을 추가해주었다.

bfs함수

Queue<Node> queue = new LinkedList<>();

        int count = 0;
        visited[node.x][node.y] = true;
        queue.add(node);

        while (!queue.isEmpty()) {
            count++;
            Node current = queue.poll();

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                if(visited[nx][ny]) continue;

                if(map[nx][ny] != 0){
                    visited[nx][ny] = true;
                    queue.add(new Node(nx, ny));
                }
            }
        }

        answer.add(count);

이 후 answer의 size를 출력해주고, 오름차순으로 정렬한 answer의 원소들을 출력하여주었다.