[Algorithm] 백준 알고리즘 2667 (단지 번호 붙이기)

 

 

java코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SetNumber {
	
	static int N;
	static int map[][];
	static boolean visited[][];
	static int house[];
	static int num=1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		visited = new boolean[N][N];
		
		for(int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for(int j=0;j<N;j++) {
				map[i][j] = line.charAt(j)-'0';
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0; j<N;j++) {
				if(!visited[i][j] && map[i][j] != 0) {
					solve(i, j);
					num++;
				}
			}
		}
		house=new int [num-1];
		for(int i=0; i<N; i++) {
			for(int j=0;j<N;j++) {
				if(map[i][j]!=0) {
					house[map[i][j]-1]++;
				}
			}
		}
		
		Arrays.sort(house);
		System.out.println(num-1);
		for (int a : house)
            System.out.println(a);
	}
	
	static void solve(int a, int b) {
		int dx[] = {-1, 1, 0, 0};
		int dy[] = {0, 0, 1, -1};
		
		Queue<int[]>q=new LinkedList<>();
		q.add(new int[] {a,b});
		map[a][b] = num;
		visited[a][b]=true;
		while(!q.isEmpty()) {
			int location[] = q.poll();
			int x = location[0];
			int y = location[1];
			
			for(int i=0; i<4; i++) {
				int xx = x+dx[i];
				int yy = y+dy[i];
				if(xx>=0&&xx<N&&yy>=0&&yy<N) {
					if(map[xx][yy]!=0&&!visited[xx][yy]) {
						q.add(new int[] {xx,yy});
						visited[xx][yy]=true;
						map[xx][yy]=num;
					}
				}
			}
		}
	}

}