단지번호 붙이기 - 정올 1695번

전형적인 DFS인 단지번호 붙이기는 DFS 로직만 알고 있다면 쉽게 접근할 수 있다.

단지번호 붙이기는 그냥 숫자만 올리고, 정렬하는 것만 유의하면 된다.

특히 bubble sort를 진행할 때 어떤 블로그들에선 완전히 잘못된 내용으로 접근하는 경우가 있다. 비교를 정말 쓸데 없는 부분까지 하는경우가 있는데,

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC에 나와있는 바처럼 짧게 기술할 수 있다.

암튼 결론은 버킹검

#include<stdio.h> int N; int scan[30][30]; int Ndanji = 2; int sol[1000] = { 0, }; int cnt = 1; void danji(int x, int y) { scan[x][y] = Ndanji; if (scan[x][y + 1] == 1) { cnt++; danji(x, y + 1); } if (scan[x][y - 1] == 1) { cnt++; danji(x, y - 1); } if (scan[x - 1][y] == 1) { cnt++; danji(x - 1, y); } if (scan[x + 1][y] == 1) { cnt++; danji(x + 1, y); } } void main() { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%1d", &scan[i][j]); } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (scan[i][j] == 1) { danji(i, j); sol[Ndanji] = cnt; Ndanji++; cnt = 1; } } } int tmp; for (int i = 0; i < Ndanji; i++) { for (int j = 0; j < Ndanji -1-i; j++) { if (sol[j] > sol[j + 1]) { tmp = sol[j]; sol[j] = sol[j+1]; sol[j+1] = tmp; } } } printf("%d\n", Ndanji-2); for (int i = 2; i < Ndanji; i++) { printf("%d\n", sol[i]); } }