[백준/Java] 2667 : 단지번호붙이기(BFS)

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon_2667_단지번호붙이기_BFS {

	static int[][] map;
	static boolean[][] visit;
	static ArrayList<Integer> list;
	static int N, cnt;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());			
		map = new int[N][N];
		visit = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
        
		cnt = 0;
		list = new ArrayList<>();
		
        for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == 1 && !visit[i][j]) 
					bfs(i, j);			
			}
		}
        
		Collections.sort(list);

		System.out.println(cnt);
        
		for (int a : list) {
			System.out.println(a);
		}
		br.close();
	}

	private static void bfs(int i, int j) {
		Queue<Point> que = new LinkedList<>();
		int houseCnt = 1;

		que.offer(new Point(i, j));
		visit[i][j] = true;
		while (!que.isEmpty()) {

			Point tmp = que.poll();
			for (int k = 0; k < 4; k++) {
				int nx = tmp.x + dx[k];
				int ny = tmp.y + dy[k];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;
				if (map[nx][ny] == 1 && !visit[nx][ny]) {
					visit[nx][ny] = true;
					que.add(new Point(nx, ny));
					houseCnt++;
				}
			}
		}
		cnt++;
		list.add(houseCnt);
	}
}

class Point {
	int x;
	int y;
    
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}