백준 2667. 단지번호붙이기 (JAVA) (DFS)

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

public class Main {
	
	static int[][] arr; // 아파트의 위치를 저장할 배열 
	static boolean[][] visit; // 방문 여부를 입력할 배열 
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static int cnt ; // 단지내에 존재하는 아파트의 개수 
	static int N; // 지도의 크기 N*N
	static ArrayList<Integer> list ;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		visit = new boolean[N][N];
		
		for(int i = 0 ; i < N; i++) {
			
			String str = br.readLine();
			
			for(int j = 0 ; j < N ; j++) {
				
				char ch = str.charAt(j);
				arr[i][j] = ch - '0';
			}
		}
		
		cnt = 0;
		list = new ArrayList<>();
		
		for(int i = 0 ; i < N; i++) {
			
			for(int j = 0; j < N; j++) {
				
				if(arr[i][j] == 1 && !visit[i][j]) {
					cnt = 1;
					dfs(i,j);
					list.add(cnt); // 단지에 존재하는 아파트의 개수를 list에 저장 
				}
			}
		}
		Collections.sort(list); // 정렬해주고 
		System.out.println(list.size()); // list의 사이즈가 곧 단지의 개수 
		for(int value : list) {
			System.out.println(value);
		}	
	}
	
	static void dfs(int i, int j) {
		visit[i][j] = true;
		
		for(int z = 0 ; z < 4 ; z++) {
			
			int ni = i + dr[z];
			int nj = j + dc[z];
				
			if(ni >= 0 && nj >= 0 && ni < N && nj < N) {
				
				if(arr[ni][nj] == 1 && !visit[ni][nj]) {
	
					dfs(ni,nj);
					cnt++;
				}
			}
		}
	}
}

○ 문제 요약

지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 아파트의 수를 오름차순으로 정렬하여 출력해라.

 

○ 문제 풀이

백준 1012. 유기농 배추(JAVA) (DFS)

이전에 DFS를 이용해서 푼 1012번 문제와 풀이법은 같기 때문에 쉽게 풀 수 있었는데 출력하는 과정을 구현하는데 조금 애를 먹었다.

 

dfs() 메소드를 사용해서 현재 위치에서 상,하,좌,우에 있는 값이 1이고 visit가 false이면 해당 값이 위치한 좌표의 값으로 다시 dfs() 메소드를 실행하는 재귀 호출로 아파트의 개수를 구했다. 

 

이 과정을 수행하면 각 사각형의 안에 있는 아파트의 개수들이 나올 것이고 그것을 미리 만든 list에 넣어준다. 

그러면 list에는 위 그림처럼 [7, 8, 9] 값이 들어있고, 오름차순으로 출력하라고 했기 때문에 Collections.sort()로 오름차순 정렬을 해준다. 

 

list의 사이즈가 곧 단지의 개수를 나타내므로 list.size()를 출력해주고 향상된 for문으로 list에 있는 값을 value로 받아서 value를 출력해주면 단지의 개수와 아파트의 개수를 오름차순으로 출력할 수 있다.

 

 

(1012번과 출력을 하는 과정을 빼면 풀이 방법은 같기 때문에 dfs()메소드가 수행되는 과정은 간단하게 설명했다. 1012번에서 이것보다 자세하게 설명을 했으니 보고 온다면 코드에 대해 더 쉽게 이해가 가능할 것이다. )

○ 결과