-
2468번 안전영역 | BFS, DFS | 백준 2468 C++ 코드[백준 알고리즘]/[C++] 2021. 3. 2. 10:04728x90반응형
이번 포스팅은 백준 2468번 안전영역입니다.
아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.
기본 알고리즘
BFS 너비 우선 탐색
DFS 깊이 우선 탐색
전체 코드
BFS 너비 우선 탐색
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697//백준2468 안전영역#include <iostream>#include <queue>#include <vector>#include <algorithm>using namespace std;int N;const int MAX = 101;int input[MAX][MAX];int map[MAX][MAX];bool visited[MAX][MAX];int dy[] = { 0,0,-1,1 };int dx[] = { -1,1,0,0 };queue<pair<int, int>> q;vector<int> v; //영역 개수 저장 벡터int cnt; //영역 개수void BFS(int y, int x) {visited[y][x] = true;q.push(make_pair(y, x));while (!q.empty()) {y = q.front().first;x = q.front().second;q.pop();for (int i = 0; i < 4; i++) {int ny = y + dy[i];int nx = x + dx[i];if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;if (map[ny][nx] && !visited[ny][nx]) {visited[ny][nx] = true;q.push(make_pair(ny, nx));}}}}void reset() {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {map[i][j] = 0;visited[i][j] = 0;}}cnt = 0;}int main() {int maxHeight = -1;cin >> N;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> input[i][j];if (input[i][j] > maxHeight) {maxHeight = input[i][j];}}}for (int h = 1; h <= maxHeight; h++) {/*h미만 물에 잠김*//*h미만=0 h이상=1 */for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (input[i][j] < h) {map[i][j] = 0;}else {map[i][j] = 1;}}}/*BFS 영역 개수 구하기*/for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (map[i][j] && !visited[i][j]) {BFS(i, j);cnt++;}}}v.push_back(cnt);/*초기화*/reset();}sort(v.begin(), v.end()); //오름차순 정렬cout << v[v.size() - 1]; //최댓값 출력}cs DFS 깊이 우선 탐색
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788//백준2468 안전영역#include <iostream>#include <vector>#include <algorithm>using namespace std;int N;const int MAX = 101;int input[MAX][MAX];int map[MAX][MAX];bool visited[MAX][MAX];int dy[] = { 0,0,-1,1 };int dx[] = { -1,1,0,0 };vector<int> v; //영역 개수 저장 벡터int cnt; //영역 개수void DFS(int y, int x) {visited[y][x] = true;for (int i = 0; i < 4; i++) {int ny = y + dy[i];int nx = x + dx[i];if (ny < 0 || nx < 0 || ny >= N || nx >= N)continue;if (map[ny][nx] && !visited[ny][nx]) {visited[ny][nx] = true;DFS(ny, nx);}}}void reset() {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {map[i][j] = 0;visited[i][j] = 0;}}cnt = 0;}int main() {int maxHeight = -1;cin >> N;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cin >> input[i][j];if (input[i][j] > maxHeight) {maxHeight = input[i][j];}}}for (int h = 1; h <= maxHeight; h++) {/*h미만 물에 잠김*//*h미만=0 h이상=1 */for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (input[i][j] < h) {map[i][j] = 0;}else {map[i][j] = 1;}}}/*DFS 영역 개수 구하기*/for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (map[i][j] && !visited[i][j]) {DFS(i, j);cnt++;}}}v.push_back(cnt);/*초기화*/reset();}sort(v.begin(), v.end()); //오름차순 정렬cout << v[v.size() - 1]; //최댓값 출력}cs 728x90반응형'[백준 알고리즘] > [C++]' 카테고리의 다른 글
5014번 스타트링크 | BFS | 백준 5014 C++ 코드 (0) 2021.03.03 2589번 보물섬 | BFS | 백준 2589 C++ 코드 (1) 2021.03.03 13565번 침투 | BFS, DFS | 백준 13565 C++ 코드 (0) 2021.02.28 11123번 양 한마리... 양 두마리... | BFS, DFS | 백준 11123 C++ 코드 (0) 2021.02.25 16948번 데스 나이트 | BFS | 백준 16948 C++ 코드 (0) 2021.02.24