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

 

BFS를 이용한 문제이다. 각각의 덩어리를 만들기 위해서 2중 for문을 이용해주고, 상하좌우를 탐색하며 인근 노드들을 탐색하여 해결할 수 있다.

 

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;

class node2667 {
	int x;
	int y;

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

public class p2667 {
	public static int[] nx = { -1, 0, 0, 1 };
	public static int[] ny = { 0, 1, -1, 0 };

	public static int[][] ary;
	public static int a;
	public static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		a = Integer.parseInt(br.readLine());
		ary = new int[a][a];
		visited = new boolean[a][a];

		for (int i = 0; i < a; i++) {
			String[] s = br.readLine().split("");
			for (int j = 0; j < a; j++) {
				ary[i][j] = Integer.parseInt(s[j]);
			}
		}

		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < a; i++) {
			for (int j = 0; j < a; j++) {
				if (visited[i][j] == false && ary[i][j] == 1) {
					list.add(bfs(i, j));
				}
			}
		}

		System.out.println(list.size());
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}

	}

	public static int bfs(int row, int col) {
		int count = 1;
		Queue<node2667> q = new LinkedList<>();
		q.add(new node2667(row, col));

		visited[row][col] = true;
		while (!q.isEmpty()) {
			node2667 n = q.poll();

			for (int i = 0; i < 4; i++) {
				int x = n.x + nx[i];
				int y = n.y + ny[i];
				if (x >= 0 && y >= 0 && x < a && y < a) {					
					if (ary[x][y] == 1 && visited[x][y] == false) {
						q.add(new node2667(x, y));
						visited[x][y] = true;
						count++;
					}
				}
			}
		}
		return count;
	}
}