[백준] 2667. 단지번호붙이기 - 실버1

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

2667번: 단지번호붙이기

 

문제 요약

정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

문제 해결 아이디어

섬의 개수와 유사한 문제다. visited[][] 배열로 각 좌표를 방문했는지 관리해 주며, 방문하지 않은 1의 좌표에 대해 dfs를 돈다.

N의 최대값이 25기 때문에 단지의 개수는 최대 625개가 나올 수 있기 때문에 단지에 속하는 집의 수를 넣는 배열인 num을 625만큼 할당해 줬다. dfs를 돌면서 속한 집의 수를 sum에 저장하고, 단지 수에 해당하는 인덱스에 sum을 저장한다.

 

완성된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	/*
	 * 100ms
	 */
	static int N, map[][], num[], sum;
	static boolean visited[][];

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

		String str;
		for (int i = 0; i < N; i++) {
			str = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					sum = 0;
					dfs(i, j);
					num[cnt++] = sum;
				}
			}
		}
		System.out.println(cnt);
		Arrays.sort(num, 0, cnt);
		for (int i = 0; i < cnt; i++) {
			System.out.println(num[i]);
		}
	}

	private static void dfs(int i, int j) {
		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };

		visited[i][j] = true;
		sum++;
		for (int p = 0; p < 4; p++) {
			int nr = i + dr[p];
			int nc = j + dc[p];

			if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc] && map[nr][nc] == 1) {
				dfs(nr, nc);
			}
		}

	}
}