fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int Box[27][27]; int Visited[27][27]; Queue[9990000]; int H_cnt[500];
  5. int Queue_cnt, Qx, Qy, rear, front, H, N, Sx, Sy, cnt;
  6.  
  7. void Q_Init() {
  8. 	for (int i = 0; i < 9990000; i++) { Queue[i] = 0; Queue_cnt = 0; rear = 0; front = 0; Qx = 0; Qy = 0; }
  9. }
  10. int isEmpty() {
  11. 	if (rear == front) { return 1; }
  12. 	else { return 0; }
  13. }
  14. void push(int a, int b) {
  15. 	if (rear < 9990000) {
  16. 		Queue[rear++] = a; Queue[rear++] = b; Queue_cnt++;
  17. 	}
  18. }
  19. void pop() {
  20. 	if (!isEmpty()) {
  21. 		Qx = Queue[front++]; Qy = Queue[front++]; Queue_cnt--;
  22. 	}
  23. }
  24. void Start_Point() {//Box를 돌면서 최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
  25. 	int flag = 0;
  26. 	for (int i = 1; i <= N; i++) {
  27. 		for (int j = 1; j <= N; j++) {
  28. 			if (Box[i][j] == 1 && flag == 0) { Sx = i; Sy = j; flag = 1; }
  29. 		}
  30. 	}
  31. }
  32. int bfs(int a, int b) {
  33. 	push(a, b); int House = 0;
  34. 	while (!isEmpty()) {
  35. 		pop(); a = Qx; b = Qy; 
  36. 		if (Box[a][b] != 0) {//pop 해 준 항목은 0으로 함.
  37.             // 해당 Box값을 0으로 해 주고, 총 집의 개수(H)에서 방문한 집을 --, 해당 단지내의 집의 수를 ++한다
  38. 			House++; H--; Box[a][b] = 0;
  39. 		}
  40. 		//if(상하좌우에 1이 있고, 방문한 기록이 없으면, --> 해당 셀의 주소를 큐에 push 하고, 방문한 기록을 남긴다)
  41. 		if (Box[a + 1][b] == 1 && Visited[a + 1][b] != 1) { push(a + 1, b); Visited[a + 1][b]; }
  42. 		if (Box[a - 1][b] == 1 && Visited[a - 1][b] != 1) { push(a - 1, b); Visited[a - 1][b]; }
  43. 		if (Box[a][b + 1] == 1 && Visited[a][b + 1] != 1) { push(a, b + 1); Visited[a][b + 1]; }
  44. 		if (Box[a][b - 1] == 1 && Visited[a][b - 1] != 1) { push(a, b - 1); Visited[a][b - 1]; }
  45. 	}
  46. 	return House;
  47. }
  48. void swap(int a, int b) {
  49. 	int tmp = a; a = b; b = tmp;
  50. }
  51. int main() {
  52. 	scanf("%d", &N);
  53. 	for (int i = 1; i <= N; i++) { 
  54. 		for (int j = 1; j <= N; j++) {
  55. 			scanf("%1d", &Box[i][j]);
  56. 			if (Box[i][j] == 1) { H++; } //집의 총 개수 H를 카운트 해 준다
  57. 		}
  58. 	}
  59. 	while (H) {  // H : 집의 개수. 집의 개수가 0이 될때 까지 돌린다 (집의 개수는 방문 할때마다 H-- 해 준다)
  60. 		Start_Point(); //최초로 만나는 1을 Start_Point로 해서 Sx, Sy 값을 설정하는 함수
  61. 		H_cnt[cnt++] = bfs(Sx, Sy); //단지 0, 1, 2번의 집의 개수 :  H_cnt[0], H_cnt[1], H_cnt[2] ...
  62. 	}
  63. 	//H_cnt[] 배열의 각 요소를 오름차순으로 정렬
  64. 	for (int k = 0; k < cnt; k++) { //단지 개수만큼 돌린다
  65. 		for (int i = 0; i < cnt; i++) {
  66. 			if (H_cnt[i] > H_cnt[i + 1]) { swap(H_cnt[i], H_cnt[i + 1]); }
  67. 		}
  68. 	}
  69. 	printf("%d", cnt); //단지 개수 출력
  70. 	for (int i = 0; i < cnt; i++) { // 단지 별 가장 작은 수 부터 출력
  71. 		printf("\n%d", H_cnt[i]);
  72. 	}
  73. }
Success #stdin #stdout 0s 48456KB
comments (?)
stdin
copy 
6
111111
100001
100101
101001
100001
111111
stdout
copy 
3
20
1
1
https://ideone.com/hGUjGm
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!