[백준] 2667 단지번호붙이기

 

문제 출처 
https://www.acmicpc.net/problem/2667

 

DFS를 이용해서 풀었다

public class back2667 {
	static int[] rowD = {-1,1,0,0};//상하좌우
	static int[] colD = {0,0,-1,1};//상하좌우
	static int num;
	static boolean[][] arrCheck;
	static List<Integer> list = new ArrayList<Integer>();
	static int[][] arr;
	static int count;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		num = sc.nextInt();
		sc.nextLine();
		
		arr = new int[num][num];
		arrCheck =  new boolean[num][num];	
		
		//입력받기
		for(int i=0;i<num;i++) {
			String str = sc.next();
			for(int j=0;j<num;j++) {
				arr[i][j] =Integer.parseInt(str.charAt(j)+"") ;
			}
		}
		
		
		for(int i=0;i<num;i++) {
			for(int j=0;j<num;j++) {
				//0인경우
				if(arr[i][j]==0) {
					arrCheck[i][j] = true;
					continue;
				} 
				//이미 갔던 경유
				if(arrCheck[i][j]) continue;
				
				// DFS실행
				if(arr[i][j]==1 && !arrCheck[i][j]) {
					arrCheck[i][j]=true;
					count++;
					DFS(i,j);
					list.add(count);
					count = 0;
				}
			}
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for(int i=0;i<list.size();i++) {
			System.out.println(list.get(i));
		}
	}
	
	public static void DFS(int Starti,int Startj) {
		for(int i=0;i<4;i++) {
			int row = Starti + rowD[i]; 
			int col = Startj + colD[i]; 
			
			if(row>=0&&row<num&&col>=0&&col<num) {
				if(arr[row][col]==1&&arrCheck[row][col]==false) {
					arrCheck[row][col] = true;
					count++;
					DFS(row,col);
				}
			}
		}
		return ;
	}
}