[백준] 2667 : 단지번호 붙이기 JAVA 풀이

 

 

 

 

import java.io.*;
import java.util.*;
public class Main {
	
    // 상하좌우 이동을 위한 좌표배열
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};

	static int N; 
	
	static int[][] graph; // 지도를 저장할 배열
	static boolean[][] visit; // 방문했는지 체크하기 위한 배열
	
	static int[] aparts = new int[25*25]; // 각 단지의 아파트 수
	static int apartNum = 0; // 단지의 수
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N+1][N+1];
		visit = new boolean[N+1][N+1];
		
        // 그래프를 초기화
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<N;j++) {
				graph[i+1][j+1] = str.charAt(j)-'0';
			}
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
            	// 해당 좌표에 집이 있고 아직 방문하지 않은 집이라면
				if(graph[i][j]==1&&!visit[i][j]) {
					dfs(i,j); // 그 집에서 dfs 수행
					apartNum++; // 아파트 단지 수 증가
				}
			}
		}
		
		Arrays.sort(aparts); // 각 단지의 아파트 수를 오름차순으로 정렬
		System.out.println(apartNum); // 아파트 단지 수 출력
		
		for(int i=0;i<aparts.length;i++) {
        	// 정렬한 아파트 수 출력
			if(aparts[i]!=0) System.out.println(aparts[i]);
		}
	}
	
	static void dfs(int x, int y) {
		visit[x][y] = true;
		aparts[apartNum]++; // 해당 아파트 단지의 아파트 수 증가시킴
		
        // 인자로 받은 x, y 좌표에서 상하좌우로 이동하며 dfs 호출
		for(int i=0;i<4;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>0&&ny>0&&nx<=N&&ny<=N) {
				if(graph[nx][ny]==1&&!visit[nx][ny]) {
					dfs(nx,ny);
				}
			}
		}
	}
	
}

 

import java.io.*;
import java.util.*;
public class bj_2667 {
	
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};

	static int N; 
	
	static int[][] graph;
	static boolean[][] visit;
    
	// counter의 크기 = 단지의 수
	static ArrayList<Integer> counter = new ArrayList<Integer>();
    // 집의 수
	static int cnt = 0; 
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N+1][N+1];
		visit = new boolean[N+1][N+1];
		
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<N;j++) {
				graph[i+1][j+1] = str.charAt(j)-'0';
			}
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(graph[i][j]==1&&!visit[i][j]) {
					cnt=1; // 한 단지를 탐색하기 시작할 때 집의 수를 1로 초기화
					dfs(i,j); // 그 집에서 다시 dfs
					counter.add(cnt); // 그 단지의 집의 수 counter에 추가
				}
			}
		}
		
		Collections.sort(counter); // 집의 수 오름차순으로 정렬
		System.out.println(counter.size()); // 단지의 수 출력
		for(int num : counter) System.out.println(num);
		
	}
	
	static void dfs(int x, int y) {
		visit[x][y] = true;
		
		for(int i=0;i<4;i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(nx>0&&ny>0&&nx<=N&&ny<=N) {
				if(graph[nx][ny]==1&&!visit[nx][ny]) {
					dfs(nx,ny);
					cnt++; // 집의 수 +1
				}
			}
		}
	}
	
}