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

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

 

접근

DFS 또는 BFS를 이용하여 각 단지 내에 있는 집의 수를 구하고 리스트에 추가합니다. 그리고 오름차순으로 정렬하면 문제를 해결할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static int n, count;
	static int[][] map;
	static boolean[][] visited;

	// 상, 하, 좌, 우
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static ArrayList<Integer> houseCounts = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력 처리
		n = Integer.parseInt(br.readLine());

		map = new int[n][n];
		visited = new boolean[n][n];

		for (int i = 0; i < n; i++) {
			char[] input = br.readLine().toCharArray();
			for (int j = 0; j < n; j++) {
				map[i][j] = input[j] - '0';
			}
		}

		// dfs를 이용하여 단지에 번호를 붙이고 연결한다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					count = 1;
					visited[i][j] = true;
					dfs(i, j);
					houseCounts.add(count);
				}
			}
		}

		// 각 단지 내 집의 수를 오름차순으로 정렬
		Collections.sort(houseCounts);

		// 결과 출력
		System.out.println(houseCounts.size());
		for (int count : houseCounts) {
			System.out.println(count);
		}
	}

	static void dfs(int r, int c) {
		for (int dir = 0; dir < 4; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			if (inRange(nr, nc) && !visited[nr][nc] && map[nr][nc] == 1) {
				visited[nr][nc] = true;
				count++;
				dfs(nr, nc);
			}
		}
	}

	static boolean inRange(int r, int c) {
		return 0 <= r && r < n && 0 <= c && c < n;
	}
}