가장 큰 섬 찾기

ㄹ #include<iostream> #include<fstream> #include<vector> #include<string> #include<map> #include<algorithm> using namespace std; map<int, int> m; void areaTraversal(string arr[], int map[][100], int x, int y, int k) { if (x < 0 || y < 0 || x > arr[0].length() || y > arr[0].length()) { return; } if (arr[x][y] == '1' && map[x][y] == 0) { m[k] = (m.find(k) != m.end() ? m[k] + 1 : 1); map[x][y] = k; areaTraversal(arr, map, x + 1, y, k); areaTraversal(arr, map, x - 1, y, k); areaTraversal(arr, map, x, y + 1, k); areaTraversal(arr, map, x, y - 1, k); } } int main() { ifstream in("in.txt"); int size = 0; string arr[10]; int map[100][100] = { 0, }; vector<int> area; if (in.is_open()) { in >> size; for (int i = 0; i < size; i++) { in >> arr[i]; } } int k = 1; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (arr[i][j] == '1' && map[i][j] == 0) { areaTraversal(arr, map, i, j, k++); } } } int max = -1; for (auto e : m) { if (e.second > max) max = e.second; } cout << max << endl; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { cout << map[i][j]; } cout << endl; } }

주어진 2차원 배열에서 가장 많은 1을 가진 섬을 찾는 문제

recursive를 사용한 DFS로 간단하게 작성