[BFS / DFS] [백준 / 2667 ] 실버1 - 단지번호붙이기 (java/자바)

문제

성공 코드

package newboj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class boj_2667 {
    static int map[][];
    static boolean isVisited[][];
    static int N;
    static int[] dy = new int[]{-1,1,0,0};
    static int[] dx = new int[]{0,0,1,-1};
    static List<Integer> countHome = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(r.readLine());
        map= new int[N][N];
        isVisited= new  boolean[N][N];

        for(int i=0; i<N; i++){
            map[i] = Arrays.stream(r.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        }

        for(int i=0; i<N;i++){
            for(int j=0; j<N; j++){
                if(isVisited[i][j]==false && map[i][j]==1){
                    int getCount = dfs(new Point(i, j));
                    countHome.add(getCount);
                }
            }
        }
        Collections.sort(countHome);
        System.out.println(countHome.size());
        for (int homeCount : countHome) {
            System.out.println(homeCount);
        }
    }
    static int dfs(Point currentPoint){
        int count = 1;
        isVisited[currentPoint.y][currentPoint.x] =true;

        for(int i=0; i<4;i++){
            int nextY = currentPoint.y + dy[i];
            int nextX = currentPoint.x + dx[i];

            if(!(0<=nextY && nextY<N && 0<= nextX && nextX <N)) continue;
            if(map[nextY][nextX]!=1) continue;
            if(isVisited[nextY][nextX]==true) continue;
            
            count += dfs(new Point(nextY,nextX)); // 재귀적으로 방문한 집의 수를 더합니다.
        }

        return count;
    }

    static class Point{
        int y;
        int x;

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

왜 DFS로 풀었나요?

간결함과 직관성: DFS는 현재 방문한 집에서 시작하여, 가능한 깊게 연결된 집들을 탐색하며 간단하게 단지를 형성할 수 있습니다. 재귀 호출을 통해 코드를 간결하게 작성할 수 있으며, 각 단지를 따라가며 탐색하는 과정이 직관적입니다.

스택의 사용: 자연스럽게 시스템 스택을 이용한 재귀 호출로 구현할 수 있으며, 이는 각 단지 내의 깊은 연결을 따라 탐색할 때 유용합니다.

탐색 경로: DFS는 탐색을 시작한 지점에서 가능한 한 멀리 있는 지점까지 탐색한 후 다른 경로를 시도합니다. 이는 단지 내의 모든 집을 효과적으로 방문하는 데 적합한 방식입니다.

단지 번호 붙이기와 같은 문제에서는 DFS가 더 선호됩니다.
이유는 각 단지를 깊게 탐색하며 집들을 연결하는 과정이 DFS로 구현하기에 더 직관적이고 간결하기 때문입니다. 하지만, BFS를 사용하여도 문제를 해결할 수 있긴 합니다.