[알고리즘 TIL] 2667. 단지 번호

문제

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

구현 및 설명

이 문제는 그래프 탐색 문제로, 그래프 탐색에 사용할 수 있는 알고리즘으로는 DFS와 BFS가 있다.

BFS는 최단 경로 찾는 데에 효율적이고, DFS는 모든 경우의 수를 탐색하는 데 효율적이므로, 미로의 모든 지점을 순회해야하는 해당 문제에는 DFS를 활용하였다.

 

DFS를 활용하여 하나의 단지를 끝까지 탐색한 후, 해당 단지의 집의 갯수를 반환하고 새로운 단지를 탐색하도록 하였다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Q2667_단지번호붙이기 {

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static List<Integer> houseCounts = new ArrayList<>();
    static boolean[][] visited;
    static int[][] maze;
    static LinkedList<Integer[]> stack = new LinkedList<>();
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        /**
         * 미로 초기화
         */

        N = Integer.parseInt(br.readLine());
        maze = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] inputStr = br.readLine().split("");
            for (int j = 0; j < N; j++) {
                maze[i][j] = Integer.parseInt(inputStr[j]);
            }
        }

        /**
         * DFS로 순회하며 단지 수와 단지에 속하는 집의 수 탐색
         */

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (maze[i][j] == 1 && visited[i][j] == false) {
                    houseCounts.add(dfs(i, j));
                }
            }
        }

        Collections.sort(houseCounts);

        bw.write(houseCounts.size() + "\n");
        for (int i = 0; i < houseCounts.size(); i++) {
            bw.write(houseCounts.get(i) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static Integer dfs(int y, int x) {
        stack.addLast(new Integer[]{x, y});
        int houseCount = 0;

        while (!stack.isEmpty()) {
            Integer[] peekPos = stack.getLast();
            stack.removeLast();
            int peekX = peekPos[0];
            int peekY = peekPos[1];

            if (maze[peekY][peekX] == 0 || visited[peekY][peekX] == true) continue;

            houseCount++;
            visited[peekY][peekX] = true;

            for (int i = 0; i < 4; i++) {
                int nextX = peekX + dx[i];
                int nextY = peekY + dy[i];

                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
                    stack.addLast(new Integer[]{nextX, nextY});
                }
            }
        }
        return houseCount;
    }
}

느낀 점

BFS, DFS 문제에서 항상 고민되는 부분이 갯수 세기이다. BFS의 경우에는 최단 경로 구하기, DFS 경우에는 연결된 덩어리의 갯수를 구하는 경우에 count를 어느 경우에 갱신하여 result 배열에 저장해야하는지 헷갈렸다. 이 문제를 통해서 DFS에서는 한 묶음을 다 돌았을 때 count를 0부터 다시 시작하고, BFS에서는 Queue에 count를 같이 저장하여 for문을 돌며 nextX, nextY를 Queue에 저장하는 시점에 count를 갱신하면 된다. 다른 문제에서도 적용해보며 익숙해질 때까지 연습해봐야겠다.