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

 

• 상하좌우로만 이동가능
• 배열수를 입력받아서, area배열과 방문했는지 체크하는 배열 선언
• for문을 돌려서 area 배열을 채워준다.
  result는 각각의 단지들마다 수 저장하는 것
• 시작점이 주어지지 않았기 때문에
• for문을 돌려서 1이고, 방문한적이 없으면  그것이 start 지점이므로
• 이미 하나 찾았으니까 count=1로 시작하고, bfs 함수 실행 
• bfs함수는 재귀함수인데, 그안에서 for문으로 상하좌우 다 탐색하면서
• 조건에 맞으면 bfs 다시 실행시키고 count++
• arrayList에  count를 넘겨주고,
• 오름차순 출력이므로 정렬
• arrayList의 size()를 통해 총 갯수를 반환,
• for문을 통해 각각의 수를 반환

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

public class Main {
	
static int N, count;
static int[][] area ;
static boolean[][]  visited;
static int moveX[] = {-1,0,1,0};
static int moveY[] = {0,1,0,-1};
static ArrayList<Integer> result;

public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	 N=sc.nextInt();
	area=new int[N][N];
	visited=new boolean[N][N];


	for (int i = 0; i < N; i++) {
			String input=sc.next();
		for (int j = 0; j < N; j++) {
			area[i][j]=Integer.parseInt(input.charAt(j)+"");
		}
		//sc.nextLine();
		
	}
	count=0;
	result=new ArrayList<Integer>();
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(!visited[i][j] && area[i][j]==1) {
				count=1;
				bfs(i,j);
				result.add(count);
			}
		}
	}//for-i
	Collections.sort(result);
	System.out.println(result.size());
	for(int i: result) System.out.println(i);
	
	
}//main

public static int bfs(int i, int j) {
	visited[i][j]=true;
	
	
		for(int k=0; k<4; k++) {
			int nx=i+moveX[k];
			int ny=j+moveY[k];
			
			if(nx>=0&&ny>=0&& nx<N && ny<N) {
					if(area[nx][ny]==1 && !visited[nx][ny]) {
									bfs(nx,ny);
									count++;
			}
			}
		}//for
		return count;
	}//bfs
} //Main