[BOJ] 2667번 단지번호붙이기 (Java)

문제

2667번: 단지번호붙이기

풀이

사방탐색 중 깊이우선탐색(DFS)를 사용하여 해결

기본 DFS코드에 단지 내 집의 수를 저장 할 cnt배열을 추가하였다.

따로 배열을 만들어 준 이유는 마지막에 sort를 해야하기 때문.

코드

더보기

import java.io.*;
import java.util.*;

public class Main{
	static int N, idx;
	static int[][] arr;
	static int[] cnt;
	static boolean[][] visited;
	static int[] di = {-1,1,0,0};
	static int[] dj = {0,0,-1,1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		cnt = new int[N*N];
		visited = new boolean[N][N];
		idx = 0;
		
		for(int i =0 ; i < N ; i++) {
			String str = br.readLine();
			for(int j =0 ; j < N ; j++) {
				arr[i][j] = str.charAt(j)-'0';
			}
		}
		for(int i =0 ; i < N ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(arr[i][j] == 1 && !visited[i][j]) {
					dfs(i, j);
					idx++;
				}
			}
		}
		cnt = Arrays.copyOf(cnt, idx);
		Arrays.sort(cnt);
		System.out.println(idx);
		for(int i =0 ; i < idx ; i++) {
			System.out.println(cnt[i]);
		}
	}
	
	public static void dfs(int ci, int cj) {
		cnt[idx] ++;
		visited[ci][cj] = true;
		for(int i =0 ; i < 4 ; i++) {
			int ni = ci+di[i];
			int nj = cj+dj[i];
			if(0<=ni&&ni<N && 0<=nj&&nj<N && arr[ni][nj] == 1 && !visited[ni][nj]) {
				dfs(ni, nj);
			}
		}
	}
}