단지번호 붙이기

민경 :)

단지번호 붙이기

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

package com.company;

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

public class BottleNumber {

    static int N;
    static List<Integer> groups = new ArrayList<>(); //각 단지의 집 숫자


    //상하좌우
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        int[][] map = new int[N][N]; //0:집없음, 1:집있음 2:체크된 집

        for(int i=0; i<N; i++){
            String line = sc.next();

            for(int j=0; j<N; j++){
                Character c = line.charAt(j);
                map[i][j] = Integer.parseInt( c.toString() );
            }
        }


        //전체 맵 탐색
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                findGroup(map, i,j, false);
            }
        }

        //단지수
        System.out.println(groups.size());

        //각 단지 내의 집 수
        Collections.sort(groups);//오름차순 정렬
        for(int group: groups){
            System.out.println(group);
        }

    }

    static void findGroup(int[][] map, int col, int row, boolean makeGroup){
        if(map[col][row]!=1) return;

        //체크안한 집 발견
        if(map[col][row]==1){

            //해당 칸 체크
            map[col][row]=2;

            //단지 수 처리
            if(makeGroup==false){ //새로운 단지그룹 추가
                makeGroup=true;
                groups.add(1);
            }else{
                int gIdx = groups.size()-1;
                groups.set(gIdx, groups.get(gIdx)+1); //현재 단지그룹 카운트+1
            }


            //상하좌우 주변 탐색
            for(int i=0; i<4; i++){
                int nextCol = col + dy[i];
                int nextRow = row + dx[i];

                if( (0<=nextCol && nextCol<N) && (0<=nextRow && nextRow <N) ){ //탐색하고자 하는 곳이 map범위 내에 있는지 체크
                    findGroup(map, nextCol, nextRow, makeGroup);
                }
            }//for(i)
        }

    }
}

*DFS로 풀었는데 BFS로도 가능

*DFS는 재귀를 이용