티스토리 뷰
문제 출처:www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
높이가 1~100까지 있으므로 1부터 100까지 탐색을 통해 해당 높이에서 연결되어 있는 좌표의 개수를 구하면 된다.
예제를 보면 높이가 4일 때, 연결되어 있는 좌표의 개수는 5이다. 이걸 보면 DFS 혹은 BFS를 생각해 볼 수 있다.
문제를 보니 저번에 BFS로 푼 이력이 있길래 이번에는 DFS로 풀기로 하였다.
최외각 for문을통해 높이가 1~100일 경우를 가정한다.
그리고 DFS를 돌면서 방문 체크를 하므로, 한번 방문한 좌표에는 다시는 방문하지 않는다. 만약 높이가 1일 경우, 모든 좌표를 한 번에 다 방문하므로 cnt는 1이 되고 i는 하나 증가할 것이다.
이런 식으로 마지막에 Math.max를 통해 최대 안전영역의 개수를 구할 수 있다.
'알고리즘' 카테고리의 다른 글
| 백준 - 인구 이동 (0) | 2021.04.16 |
|---|---|
| 백준 - 상범 빌딩 (0) | 2021.04.15 |
| 백준 - 늑대와 양 (0) | 2021.04.09 |
| 백준 - 소가 길을 건너간 이유1 (0) | 2021.04.06 |
| 백준 - 달팽이 (0) | 2021.04.05 |