#2667 : 단지번호붙이기

풀이방법

사용된 것:

깊이우선탐색(DFS)

 

2022.05.29

지도의 모든 칸에 대하여,

해당 칸에 집이 존재하고, 아직 방문한 적이 없는 칸이라면

그 칸을 시작점으로 삼아 dfs를 수행한다.

 

dfs가 한 번 수행 될 때마다 이때 방문한 칸 수를 저장한다. 이 칸 수가 해당 단지의 집 개수이다.

개수들을 ArrayList에 차곡차곡 저장해준 뒤, (단지의 개수를 미리 알 수 없으므로 길이변경이 자유롭고 중복값을 허용하는 ArrayList를 사용하였다.)

모든 칸의 점검이 끝나면

이 개수들을 int[]에 옮겨 Arrays.sort로 오름차순 정렬한다.

이 값들을 화면에 출력해준다.

 

코드

Java(2022.05.29)

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

public class Main {
	
	static int n;	//지도의 한 변의 길이
	static boolean[][] map;		//지도
	static boolean[][] visited;	//방문여부 저장용 배열
	static int cnt;	//각 단지별 집 수를 셀 때 사용할 변수
	//아래는 상하좌우 재귀 시에 사용할 좌표변경용 배열
	static int[] r = {-1, 1, 0, 0};
	static int[] c = {0, 0, -1, 1};
	
	static void dfs(int row, int col) {
		//지도 밖이거나, 이미 방문했거나, 집이 없는 곳이면 return
		if(row<0 || col<0 || row>=n || col>=n) return;
		if(visited[row][col]) return;
		if(!map[row][col]) return;
		
		visited[row][col] = true;	//방문했음을 표시
		cnt++;	//집 수 세어주기
		//상하좌우로 재귀
		for(int i=0; i<4; i++) dfs(row+r[i], col+c[i]);
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new boolean[n][n];
		visited = new boolean[n][n];
		//지도 내용 읽어오기
		for(int i=0; i<n; i++) {
			String input = br.readLine();
			for(int j=0; j<n; j++) if(input.charAt(j)=='1')map[i][j] = true;
		}
		//깊이우선탐색을 하면서 단지마다 집 수를 answer에 저장하기
		ArrayList<Integer> answer = new ArrayList<Integer>();
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(map[i][j] && !visited[i][j]) {
					cnt = 0;
					dfs(i, j);
					answer.add(cnt);
				}
			}
		}
		//집 수를 오름차순 정렬하기
		int[] sorted = new int[answer.size()];
		for(int i=0; i<answer.size(); i++)sorted[i] = answer.get(i);
		Arrays.sort(sorted);
		
		//정답 출력
		System.out.println(answer.size());
		for(int i: sorted) System.out.println(i);
	}

}