[BOJ] 2667 단지번호붙이기

[문제]

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

 

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Solution {
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		int[][] map = new int[n][n];
		for(int i=0;i<n;i++) {
			String s = br.readLine();
			for(int j=0;j<n;j++) {
				map[i][j] = s.charAt(j) - '0';
			}
		}
		boolean[][] visit = new boolean[n][n];
		List<Integer> list = new LinkedList<>();
		int result = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(!visit[i][j] && map[i][j]==1) {
					result++;
					int cnt = 1;
					Queue<int[]> q = new LinkedList<>();
					q.offer(new int[] {i,j});
					visit[i][j] = true;
					while(!q.isEmpty()) {
						int[] curr = q.poll();
						for(int d=0;d<4;d++) {
							int nr = curr[0] + dr[d];
							int nc = curr[1] + dc[d];
							if(nr<0 || nr>=n || nc<0 || nc>=n || visit[nr][nc]) continue;
							if(map[nr][nc]==1) {
								visit[nr][nc] = true;
								q.offer(new int[] {nr,nc});
								cnt++;
							}
						}
					}
					list.add(cnt);
				}
			}
		}
		Collections.sort(list);
		System.out.println(result);
		for(int i=0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
	}
}