[BOJ] 2667번: 단지번호붙이기(DFS)

 

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

2667번: 단지번호붙이기

 

 

 

분류 : DFS, BFS

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int N,home;
    static char[][] vileage;
    static int[][] visited;
    
    public static void main(String[] args) {

        N = sc.nextInt();
        vileage = new char[26][26];
        visited = new int[26][26];
        for (int idx = 0; idx < N; idx++) {
            vileage[idx] = sc.nextLine().toCharArray();
        }
        int[] house = new int[25 * 25 + 1];
        home = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (vileage[r][c] == '1' && visited[r][c]==0) {
                    ++home;
                    DFS(r, c);
                }
            }
        }
        for(int r =0; r<N;r++)
        {
            for(int c =0; c<N;c++)
            {
                if(visited[r][c]!=0){
                    house[visited[r][c]]++;
                }
            }
        }
        out.println(home);
        Arrays.sort(house);
        for(int idx =0; idx<house.length;idx++){
            if(house[idx]!=0){
                out.println(house[idx]);
            }
        }
        out.close();
    }

    private static void DFS(int r, int c) {
        if (r < 0 || r >= N || c < 0 || c >= N || visited[r][c]!=0 || vileage[r][c] == '0')
            return;
        visited[r][c] = home;

        DFS(r + 1, c);
        DFS(r - 1, c);
        DFS(r, c + 1);
        DFS(r, c - 1);
    }
}

 

음.. DFS를 이용해서 인접한 집끼리 번호를 부여한다.

그러고 나서 House 배열을 sort 한 다음에 답을 도출해내면 완료!