[JAVA] 백준 2667번 : 단지번호붙이기(DFS)

www.acmicpc.net/problem/2667

문제

해결 방안

total이 단지 수가 되고 지도를 탐색하면서 1을 발견하면 total++을 해준다.
그리고 DFS탐색으로 통해 해당 단지에 속한 집의 갯수를 cnt에 저장하여 dfs()를 빠져나오면 ArrayList에 해당 cnt를 넣어준다.

그리고 ArrayList에 저장된 각 단지의 집의 갯수들을 정렬하여 출력해주면 된다.

코드

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

public class Main {
	
	static int n;// 지도 크기
	static int[][] maps;
	static boolean[][] visited;
	
	static int total=0; // 총 단지수
	static int cnt;
	static List<Integer> cnts = new ArrayList<>();// 각 단지에 속하는 집의 수
	
	// 북 동 남 서
	static int[] dy = {-1, 0, 1, 0}; // 세로
	static int[] dx = {0, 1, 0, -1}; // 가로

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		n = Integer.parseInt(str);
		
		maps = new int[n][n];
		visited = new boolean[n][n];
		
		for(int i=0; i<n; i++) {
			str = br.readLine();
			for(int j=0; j<n; j++) {
				maps[i][j]=Integer.parseInt(str.split("")[j]);
			}
		}
		// === 입력 끝=======
		
		// 탐색 + 단지 수 정해주기
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				cnt = 0;
				if(maps[i][j]==1 && !visited[i][j]) {
					total++;
					cnt++;
					dfs(i, j);
					cnts.add(cnt);
				}
			}
		}
		
		// 출력
		System.out.println(total);
		Collections.sort(cnts);
		for(int i=0; i<cnts.size(); i++) {
			System.out.println(cnts.get(i));
		}
		
	}
	
	static void dfs(int cy, int cx) {
		
		visited[cy][cx] = true;
		
		int ny, nx;
		for(int i=0; i<4; i++) {
			ny = cy + dy[i];
			nx = cx + dx[i];
			
			if(ny>=0 && ny<n && nx>=0 && nx<n) {
				if(!visited[ny][nx] && maps[ny][nx]==1) {
					cnt++;
					dfs(ny, nx);
				}
			}
		}
		
	}

}