[BaekJoon] 2667 단지번호붙이기

1.  문제 링크

2.  문제

요약

• 정사각형 모양의 지도에 집이 있는 곳을 1, 집이 없는 곳을 0으로 표시해놓고 위아래 혹은 좌우로 연결되어 있는 집의 모임을 단지로 정의하여 단지에 번호를 붙이려고 할 때 단지수 및 단지별 집의 수를 오름차순으로 구하는 문제입니다.
• 입력: 첫 번째 줄에 지도의 크기 N이 주어지고 그 다음 줄부터 N개의 줄은 N개의 자료(0 또는 1)가 주어집니다.
• 출력: 첫 번째 줄에 총 단지수를 출력하고 다음 줄부터 단지수의 줄은 각 단지별 집의 수를 오름차순으로 정렬하여 출력합니다.

3.  소스코드

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

public class Main {
	static int[][] map;
	static boolean[][] visited;
	static int[] complexNum;
	static int complex = 0;
	public void dfs(int x, int y) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		complexNum[complex]++;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cy >= 0 && cx < map.length && cy < map.length) {
				if(map[cx][cy] == 1 && !visited[cx][cy]) {
					dfs(cx, cy);
				}
			}
		}
	}
	
	public void getComplexNum() {
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				if(map[i][j] == 1 && !visited[i][j]) {
					complex++;
					dfs(i, j);
				}
			}
		}
		Arrays.sort(complexNum);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int size = Integer.parseInt(br.readLine());
		map = new int[size][size];
		visited = new boolean[size][size];
		complexNum = new int[size * size];
		for(int i = 0; i < map.length; i++) {
			String isHouse = br.readLine();
			for(int j = 0; j < isHouse.length(); j++) {
				map[i][j] = Integer.parseInt(isHouse.substring(j, j + 1));
			}
		}
		br.close();
		Main m = new Main();
		m.getComplexNum();
		bw.write(complex + "\n");
		for(int i = 0; i < complexNum.length; i++) {
			if(complexNum[i] != 0) {
				bw.write(complexNum[i] + "\n");
			}
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

1. 주어진 자료들을 map이라는 2차원 정수 배열에 넣고 배열의 각 자리에 방문했는지 확인하기 위한 visited라는 2차원 정수 배열을 만듭니다.
2. 배열의 각 자리를 돌면서 해당 자리가 집이 있는 곳이고 아직 방문하지 않은 곳이라면 현재 단지 번호를 나타내는 변수인 complex를 0으로 초기화했었는데 여기에 1을 더해주고 해당 자리에서 dfs를 통해 단지를 확인합니다.
3. 상,하,좌,우를 봐야하기 때문에 이에 맞게 x와 y의 위치를 옮겨줄 4자리의 정수 배열을 만들고 해당 위치를 현재 방문했기 때문에 방문여부를 true로 변경합니다.
4. 해당 위치에 있는 집이 complex 단지에 들어갈 것이므로 각 단지별 집의 수를 저장하는 배열인 complexNum 배열에 complex번째 수를 1 추가해줍니다.
5. 3번에서 만든 4자리의 정수 배열을 이용하여 상,하,좌,우를 확인하는데 각각의 위치에서 행과 열이 0보다 크거나 같고 지도의 크기보다 작으며 해당 위치에 집이 있고 아직 방문하지 않았다면 해당 위치에서 인접하는 집이 더 있는지 확인하기 위해 해당 위치에서 3~5번 과정을 반복합니다.
6. 지도의 모든 곳을 확인할 때까지 2~5번의 과정을 반복하고 모두 확인했다면 각 단지별 집의 수를 나타내는 complexNum 배열을 오름차순으로 정렬합니다.
7. 현재 단지의 번호를 나타내는 변수인 complex가 곧 현재 만들어진 단지의 개수이기 때문에 이를 먼저 출력하고 오름차순으로 정렬한 complexNum의 값들을 순차적으로 출력합니다.