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

문제

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

2667번: 단지번호붙이기

 

 

코드

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

public class Main {
	static int n;
	static int arr [][];
	static boolean check [][];
	static int house [];
	static int dx [] = {-1,0,1,0};
	static int dy [] = {0,-1,0,1};
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		arr = new int [n][n];
		check = new boolean [n][n];
		house = new int [n*n + 1];
		
		for(int i=0;i<n;i++){
			String str = br.readLine();
			for(int j=0;j<n;j++){
				arr[i][j] = str.charAt(j) - '0';
			}
		}		
		
		int idx = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(arr[i][j] == 0 || check[i][j])
					continue;
				house[idx++] = bfs(i, j);
			}
		}
		
		Arrays.sort(house, 0, idx);
		
		System.out.println(idx);
		for(int i=0;i<idx;i++) {
			System.out.println(house[i]);
		}
	}
	
	static int bfs(int x, int y) {
		Queue<Info> que = new LinkedList<>();
		int count = 0;
		
		que.add(new Info(x, y));
		check[x][y] = true;
		count++;
		
		while(!que.isEmpty()) {
			Info cur = que.poll();
			
			for(int i=0;i<4;i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >=n || ny >= n) continue;
				if(arr[nx][ny] == 0) continue;
				if(check[nx][ny]) continue;
				
				que.add(new Info(nx, ny));
				check[nx][ny] = true;
				count++;
			}
		}
		return count;
		
	}
	
	static class Info implements Comparable<Info>{
		int x;
		int y;

		public Info(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public int compareTo(Main.Info o) {
			return x - o.x;
		}
		
	}
}