백준 - 2667번 단지번호붙이기 - java

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

접근법

DFS나 BFS나 상관없이 가능해보임
1. 지도에서 1인데, 방문하지 않은 지점을 맞이하면
2. 그 Point부터 BFS 혹은 DFS 탐색
3. 방문할때마다 visit 배열 마킹해가며 해당 Point로 시작한 경우 단지의 크기를 count해줌
4. 함수의 return 값을 단지의 크기로 하고, 그 값을 자료구조에 담음
5. 출력할땐 정렬시키고 출력

소스

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] board;
	static boolean[][] visit;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		board = new int[n][n];
		for(int i = 0; i < n; i++) {
			String s = sc.next();
			for(int j = 0; j < s.length(); j++) {
				int num = Integer.parseInt(s.substring(j, j+1));
				board[i][j] = Integer.parseInt(s.substring(j, j+1));
			}
		}
		visit = new boolean[n][n];
		ArrayList<Integer> ans = new ArrayList<Integer>();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(board[i][j] == 1 && !visit[i][j]) {
					ans.add(bfs(i, j));
				}
			}
		}
		Collections.sort(ans);
		System.out.println(ans.size());
		for(int value: ans) {
			System.out.println(value);
		}
	}
	static int bfs(int x, int y) {
		Queue<Point> q = new LinkedList<Point>();
		int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		q.offer(new Point(x, y));
		visit[x][y] = true;
		int count = 1;
		while(!q.isEmpty()) {
			Point cur = q.poll();
			
			for(int i = 0; i < dir.length; i++) {
				int nextX = cur.x + dir[i][0];
				int nextY = cur.y + dir[i][1];
				
				if(nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board.length) continue;
				if(board[nextX][nextY] == 1 && !visit[nextX][nextY]) {
					q.offer(new Point(nextX, nextY));
					visit[nextX][nextY] = true;
					count++;
				}
			}
		}
		return count;
	}
}
class Point{
	int x;
	int y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}