[BOJ] 2667 - 단지번호붙이기

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

난이도: 실버 1

사용 언어: JAVA

 

아래의 그림 1과 2와 같이 한 변의 길이가 N인 정사각형 모양의 지도가 있고, 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타냅니다. 집이 연결되어 있으면, 이를 단지라고 정의하고, 단지에 번호를 붙입니다. 여기서 연결되어 있다는 말은 어떤 집의 좌우 또는 아래위로 다른 집이 위치해있는 경우를 뜻합니다. 대각선에 위치하는 집은 연결되어 있지 않다고 간주됩니다. 

 

 

지도를 입력으로 받아, 단지의 개수와, 각 단지에 속하는 집의 수를 오름차순으로 정렬하는 문제입니다. 

 

풀이

이 문제는 DFS를 이용하여 해결할 수 있습니다. DFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/65

[BOJ] 1303 - 전쟁 - 전투

 

우선 입력 값을 이용해 지도를 2차원 배열로 표현합니다. 입력값에 지도를 표현하는 숫자들이 공백없이 표현되어 있기 때문에 nextint()로 값을 받을 수 없어, 한 줄 단위로 String 형식으로 받아서, charAt()함수를 이용해 char 크기로 잘라 배열에 넣어주었습니다.

 

그리고 (0,0)부터 (N,N)까지 반복문을 돌며 DFS를 수행합니다. 한 번이라도 지나간 곳은 0으로 변경해주어 중복으로 검사되는 일이 없도록 했습니다. DFS는 재귀 함수를 이용해 구현하였고, DFS 함수 안에서 배열의 크기를 벗어나지 않도록 조건문을 통해 검사를 해주었습니다.

 

또한, DFS를 수행할 때 한 단지에 해당되는 집의 수를 카운트 해 주어 별도의 배열에 하나씩 저장했고, 마지막에 해당 배열을 정렬하여 출력하였습니다.

 

import java.util.Arrays;
import java.util.Scanner;
 
class Main {
    static int cnt=0;
    static int N;
    static int [] list = new int[10001];
 
    public static void dfs(int x, int y, char arr[][]){
        arr[x][y] = '0';
        list[cnt] += 1;
        if(y-1 >= 0)
            if(arr[x][y-1] == '1')
                dfs(x,y-1,arr);
        if(x+1 < N)
            if(arr[x+1][y] == '1')
                dfs(x+1,y,arr);
        if(y+1 < N)
            if(arr[x][y+1] == '1')
                dfs(x,y+1,arr);
        if(x-1 >= 0)
            if(arr[x-1][y] == '1')
                dfs(x-1,y,arr);
 
    }
 
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int i,j;
        N = sc.nextInt();
        char [][] arr = new char[N][N]; // N x N 크기의 2차원 배열 생성
 
        for(i=0;i<N;i++){ // 입력 값을 이용한 지도 생성
            String str = sc.next();
            for(j=0;j<N;j++){
                arr[i][j] = str.charAt(j);
            }
        }
 
        for(i=0;i<N;i++) { // DFS 수행
            for (j = 0; j < N; j++) {
                if(arr[i][j] == '1') {
                    dfs(i, j, arr);
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
        Arrays.sort(list);
        for(i=10001-cnt;i<=10000;i++)
            System.out.println(list[i]);
 
    }
}