알고리즘 풀이/백준

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

배게 2018. 5. 19. 03:11
728x90

길이와 좌표 모두 받고


단지 구분하는 함수 (DJSetting)를 정의함


0~T 행, 0~T열 쭉 돌리면서


1이 나타나면 DJSetting 시작


상하좌우 돌리면서 1일 경우, 방문하지 않은 경우 (nVisited가 true인 경우)


2가지 조건을 충족할 시 num++해주면서


그 좌표로 다시 DJsetting 시작


전부 다 돌리고난 후의 num( 임의의 단지의 아파트 수 )


를 ArrayList에 추가 ( 단지가 몇개가 될지 몰라서 List로 저장함 )


그 후 ArrayList 오름차순 정렬 후


size와 성분 모두 출력


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static int[] X= {0,0,1,-1};
	static int[] Y= {-1,1,0,0};
	static int num;
	static int[][] dj;
	static boolean[][] nVisited;
	static int T;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		T = sc.nextInt();
		dj = new int[T][T];
		nVisited = new boolean[T][T];

		sc.nextLine();
		for(int i=0; i<T; i++) {
			String input=sc.nextLine();
			
			for(int j=0; j<T; j++) {
				dj[i][j]=input.charAt(j)-'0';
				if(dj[i][j]==1) nVisited[i][j]=true;
			}
		}
		
		/*for(int i=0; i<T; i++) {
			
			for(int j=0; j<T; j++) {
				System.out.print(dj[i][j]);
			}
			System.out.println();
		}*/
		
		ArrayList<Integer> res = new ArrayList<Integer>();
		
		for(int i=0; i<T; i++) {
			for(int j=0; j<T; j++) {
				if(nVisited[i][j]) {
					num=1;
					nVisited[i][j]=false;
					DJSetting(i,j);
					res.add(num);
				}
			}
		}
		
		Collections.sort(res, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o1.compareTo(o2);
			}
		});
		
		System.out.println(res.size());
		for (Integer integer : res) {
			System.out.println(integer);
		}
		
		
	}
	public static void DJSetting(int i,int j) {
		for(int d=0; d<4; d++) {
			if( (i+X[d]>=0 && i+X[d]<T) && (j+Y[d]>=0 && j+Y[d]<T) ) {
				if( dj[i+X[d]][j+Y[d]]==1 && nVisited[i+X[d]][j+Y[d]]) {
					num++;
					nVisited[i+X[d]][j+Y[d]]=false;
					DJSetting(i+X[d],j+Y[d]);
				}
			}
		}
	}
	
}