[백준 2667 : 단지번호 붙이기] Java, DFS

단지 번호 붙이기를 DFS로 풀어보았습니다.

개인적으로 BFS보다 DFS가 코드가 간결하고 쉽네요.

find 함수에서,

주어진 좌표의 사방을 돌면서 조건에 만족하는 값에 대해서 다시 find 함수를 호출하게 됩니다.

그와 동시에 cnt 값을 증가시킵니다.

만약 사방을 둘러보았는데 조건에 맞는 값이 없을 때는 cnt 값을 리턴해서 ArrayList에 값을 추가합니다.

이렇게 반복해서 총 단지 수는 ArrayList의 사이즈로,

단지 내의 집의 수는 ArrayList내에 저장된 값으로 출력해줍니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
 
public class Main {
    static int[][]map;
    static int N,cnt;
    static int[][]visited;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,-1,1};
    
    static ArrayList al = new ArrayList();
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        
        N = scan.nextInt();
        
        map = new int[N][N];
        visited = new int[N][N];
        
        for(int i=0;i<N;i++)
        {
            String input = scan.next();
            for(int j=0;j<N;j++)
            {
             map[i][j] = input.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] == 0)    
                {
                    cnt = 1;
                    find(i,j);
                    al.add(cnt);
                }
        }
        
        Collections.sort(al);
        
        System.out.println(al.size());
        
        for(int i=0;i<al.size();i++)
            System.out.println(al.get(i));
 
    }
    
    static int find(int x, int y) 
    {
        visited[x][y] = 1;
        
        for(int i=0;i<4;i++)
        {
        int nx = x+dx[i];
        int ny = y+dy[i];
        
        if(nx>=0&&ny>=0&&nx<N&&ny<N) {
                if(map[nx][ny] == 1 && visited[nx][ny] == 0)
                {
                    find(nx,ny);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
}