[백준] 2667번 단지번호붙이기 (java)

<문제>

문제 출처 : https://www.acmicpc.net/problem/2667

<나의 풀이>

import java.util.*;

public class Main{

    static int n, count;
    static int [][] arr;

    public static void main(String[] args){
    
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n][n];
        ArrayList<Integer> answer = new ArrayList<>(); // 정답을 담아줄 리스트
        sc.nextLine();	
        
        // 값을 입력 받아 배열에 넣어주기
        for(int i=0; i<n; i++){
            String line = sc.next();
            for(int j=0; j<n; j++){
                arr[i][j] = line.charAt(j) - '0' ;   // 아스키코드 정수로 전환
            }
        }
        
        // 모든 행렬을 돌면서 노드가 연결되어있는지 확인하고 방문처리하기
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(dfs(i,j)){
                    answer.add(count);
                    count =0;
                }
            }
        }
        Collections.sort(answer);    // 값 오름차순 정렬
        System.out.println(answer.size());
        for(int i : answer){
            System.out.println(i);
        }
    } 
    
    static boolean dfs(int x, int y){
        // 조건 확인하기
        // 1) 범위내에 들어오는지 확인하기
        if (x<0||x>=n||y<0||y>=n) return false;
        // 2) 방문 여부 확인하기 -> 왜냠 모든 행렬의 값을 돌기 때문.
        if(arr[x][y]==1){
            arr[x][y] =0; // 방문처리
            count ++; // 집의 개수 세주기
            
            // 3) 재귀 돌며 상하좌우 확인하기
            dfs(x-1,y); // 상
            dfs(x+1,y); // 하
            dfs(x,y-1); // 좌
            dfs(x,y+1); // 우     
            return true;    // 이러면 하나만 맞아도 true
        }
        return false; //  조건에 안맞으니 false 처리해주기
    }
    
}

<핵심 개념>

dfs의 개념을 알아도 어려웠다. 왜냠 이어져있는 노드의 순서를 구하는 방법은 알았어도
행렬에서 이어져있는 부분만 탐색한다는 발상을 못했기 때문. 다들 천잰가?
이코테의 얼음얼려먹기 풀이를 참고해서 어찌저찌 응용해서 풀었다.
다시 복습해보고 유형을 여러번 반복해봐야겠다.
아.. bfs로도 풀어봐야지.