https://www.acmicpc.net/problem/2667
STL을 자꾸 쓰니까 실력이 줄어드는 것 같아서..
STL없이 구현해보려고 노력하고 있습니다.
동서남북으로 연결된 지역은 같은 단지로 취급합니다.
dfs를 통해서 수를 체크하여 리턴시키고
삽입정렬로 그 개수를 정렬했습니다.
어렵지 않은 문제입니다.
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 | #include <iostream> #include <string> using namespace std; string map[25]; bool visit[25][25]; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; int n; int max(int a, int b) { return a > b ? a : b; } int dfs(int x, int y) { if (visit[x][y]) return 0; visit[x][y] = 1; int ret = 1; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n || map[nx][ny] == '0') continue; ret += dfs(nx, ny); } return ret; } void sort(int *arr, int size, int value) { int i = size - 1; while (i >= 0 && arr[i] > value) { arr[i + 1] = arr[i]; i--; } arr[++i] = value; } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> map[i]; } int ret = 0; int cnt[25 * 25]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] == '0') continue; int tmp = dfs(i, j); if (tmp) { sort(cnt, ret, tmp); ret++; } } } cout << ret<<'\n'; for (int i = 0; i < ret; i++) { cout << cnt[i] << '\n'; } return 0; } | cs |
'알고리즘 > 탐색' 카테고리의 다른 글
[2178] 미로 탐색 (0) | 2017.09.15 |
---|---|
[10216] Count Circle Groups (0) | 2017.08.10 |
[10451] 순열 사이클 (0) | 2017.07.27 |
[10974] 모든 순열 (2) | 2017.07.27 |
[1058] 친구 (0) | 2017.07.20 |