[알고리즘][BOJ][2667] 단지번호 붙이기

[알고리즘][BOJ][2667] 단지번호 붙이기

 

 

 

 

문제

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

 

 

풀이

DFS를 이용해 탐색하며 단지의 수와 단지 내 집의 수를 구해주면 되는 문제입니다. 단지의 수를 카운팅할 때는 count변수를 두었습니다. 새로운 단지일 때, count변수를 이용하여 ArrayList에 단지를 추가해줍니다. DFS함수로 들어갔을 때, h_num의 값을 증가시켜 집의 수를 구해줍니다. 탐색을 마치고 새로운 단지를 발견했을 때, count변수를 증가시키고 반복합니다.

 

코드

package algorithm_review;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class q_2667 {
    static int n;
    static int[][] area;
    static boolean[][] chk;
    static ArrayList<Integer> house_num;
    static int count;
    static int h_num;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String word = scan.nextLine();
        n = Integer.parseInt(word);
        
        area = new int[n][n];
        chk = new boolean[n][n];
        house_num = new ArrayList<>();
        for(int i=0;i<n;i++) {
            word = scan.nextLine();
            String[] arr = word.split("");
            for(int j=0;j<n;j++) {
                area[i][j] = Integer.parseInt(arr[j]);
            }
            
        }    
        count = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(area[i][j]==1 && chk[i][j]==false) {
                    h_num = 0;
                    house_num.add(count);
                    dfs(i,j);
                    house_num.set(count, h_num);
                    count++;
                }
                
            }
        }
        
        System.out.println(count);
        Collections.sort(house_num);
        for(int i=0;i<house_num.size();i++) {
            System.out.println(house_num.get(i));
        }
        
    }
    
    static void dfs(int p, int q) {
        
        h_num++;
        chk[p][q] = true;
        
        for(int i=0;i<4;i++) {
            int x = p+dx[i];
            int y = q+dy[i];
            if(x<0||x>=n||y<0||y>=n) {
                continue;
            }
            if(chk[x][y]==false && area[x][y]==1) {
                dfs(x,y);
            }
        }
    }
    
    

}