[Silver I/JAVA] 2667 단지번호붙이기

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

 

 

풀이

• 이전에 풀었던 영역구하기와 유사한 문제다. (https://marginata.tistory.com/173)
• 영역구하기가 색칠되지 않은 영역의 넓이를 구한것이라면 반대로 단지번호붙이기는 집이 있는곳의 넓이를 구하면 된다.
• 주의할 점은 0001010 이런식으로 공백없이 입력을 받기 때문에 charAt()을 이용해서 한자리씩 char형으로 추출한 뒤에 정수형으로 변환해줘야 한다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main{
    static int[][] map; //지도
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static int N; //지도 크기
    static int cnt; //집의 수
    static ArrayList<Integer> list = new ArrayList<>(); //집의 수 결과 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        //map 크기
        map = new int[N][N];
        
        //map 초기화
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        //DFS 탐색
        for(int x=0; x<N; x++){
            for(int y=0; y<N; y++){
                if(map[x][y]==1){
                    cnt=0;
                    dfs(x,y);
                    list.add(cnt);
                }
            }
        }
        
        //출력
        System.out.println(list.size());
        
        Collections.sort(list);
        for(Integer n : list){
            System.out.println(n);
        }
    }
    
    //DFS 탐색
    private static void dfs(int x, int y){
        map[x][y]=0; //집이 없으면
        cnt++;
        
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx>=0 && nx<N && ny>=0 && ny<N){
                if(map[nx][ny]==1){ //집이 있으면 탐색 계속
                    dfs(nx, ny);                        
                }
            }
        }
    }
}