[백준]Q2667 단지번호 붙이기(java, DFS알고리즘)

 

 

백준 단지번호 붙이기. 

 

DFS를 이용했다.

 

 

 

 

 

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
 
class Q2667{
    static public char[][] map;
    static public int[] x = {-1,0,1,0};
    static public int[] y = {0,1,0,-1};
    static public int[][] visit;
    static public int cnt =0;
    static public int N;
    static public ArrayList<Integer> houseNum = new ArrayList<Integer>();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        N = Integer.parseInt(scan.nextLine());
        map = new char[N][N];
        visit = new int[N][N];
        String temp;
 
        for(int i=0; i<N; i++){
            temp = scan.nextLine();
            for(int j=0; j<N; j++){
                map[i][j] = temp.charAt(j);
            }
        }
 
 
        for(int i=0; i<N ; i++){
            for(int j=0; j<N; j++){
                if(map[i][j] =='1' && visit[i][j] == 0){
                    cnt = 1;
                    visit[i][j] = 1;
                    dfs(i,j);
                    houseNum.add(cnt);
                }
                    
            }
        }
 
        Collections.sort(houseNum);
 
        System.out.println(houseNum.size());
        for(int i=0; i<houseNum.size(); i++){
            System.out.println(houseNum.get(i));
        }
 
 
    }
 
    static public void dfs(int i, int j){
        
        for(int k=0; k<4; k++){
            int ni = i + x[k];
            int nj = j + y[k];
            if(ni>=0 && ni<N && nj >=0 && nj<N){
                if(visit[ni][nj]==0 && map[ni][nj] == '1'){
                    visit[ni][nj] = 1;
                    cnt++;
                    dfs(ni, nj);
                }
            }
        }
 
    }
}