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

2667번

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

public class Main{

	static int dx[] = {0, 0, 1, -1};
	static int dy[] = {1, -1, 0, 0};
	static int[] apart = new int[25*25];
	static int n;
	static int apartNum = 0;
	static boolean[][] visited = new boolean[25][25];
	static int[][] map = new int[25][25];

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(bf.readLine());

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

		for (int i = 0; i<n; i++) {
			String input = bf.readLine();
			for (int j = 0; j<n; j++) {
				map[i][j] = input.charAt(j)-'0';
			}
		}

		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					apartNum++;
					dfs(i, j);
				}
			}
		}

		Arrays.sort(apart);
		System.out.println(apartNum);

		for (int i = 0; i<apart.length; i++) {
			if (apart[i] == 0) {
			} else {
				System.out.println(apart[i]);
			}
		}
	}

	static void dfs(int x, int y) {
		visited[x][y] = true;
		apart[apartNum]++;

		for (int i = 0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
				if (map[nx][ny] == 1 && !visited[nx][ny]) {
					dfs(nx, ny);
				}
			}
		}
	}
}

풀이

---

정접으로 연결된 묶음이 몇개 있는지와 그 묶음에 정점이 몇개있는지 나타내는 문제다.

기존의 dfs문제에서 정점이 몇개있는지 세주기만 하면 되는문제다.

좌우를 나타내는 dx 상하를 나타내는 dy를 써서 상하좌우에 1이 있으면 계속 탐색하면서 카운팅을 한다. 묶음 탐색이 끝나면 다음 묶음을 찾는다.

상하좌우를 살피는 것이 생소한 방법이지만 다음에 나온다면 어렵지 않게 풀 수 있을것이라 생각한다.