문제: https://www.acmicpc.net/problem/2468
알고리즘 분류: 너비 우선 탐색, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색
컨디션 이슈
- 감기에 제대로 걸려서 오늘 하루 책상에 앉아있는 게 고역이었다
- 3시간 고민하고도 문제 해결이 어려워서 이론부터 공부하기로 했다
- 구글링과 ai의 힘을 빌려 힌트를 얻고, 답을 완성해나갔다
- 더 나은 개선방안이 있는 지 추후 고민하고 정리해보려고 한다
문제 요약
- N×N 크기의 2차원 배열에 각 지점의 높이가 주어진다
- 비가 내려 특정 높이 이하의 지점이 모두 물에 잠긴다
- 물에 잠기지 않는 안전한 영역이란 물에 잠기지 않는 지점들이 상하좌우로 인접해 있는 지역이다
- 다양한 강수량(비의 양)에 따라 안전한 영역의 개수가 달라질 때, 안전한 영역의 최대 개수를 구해야 한다
접근 방법
이 지역에서 가능한 모든 강수량에 대해 시뮬레이션을 해봐야 합니다.
각 시뮬레이션에서 안전한 영역의 개수를 계산하고, 그 중 최댓값을 찾습니다.
안전한 영역의 개수는 DFS나 BFS를 이용해 구할 수 있습니다.
DFS와 BFS 개념 설명
DFS(깊이 우선 탐색)
- 그래프나 트리에서 깊이를 우선적으로 탐색하는 알고리즘
- 한 경로를 끝까지 탐색한 후 다른 경로를 탐색
- 주로 재귀 함수나 스택을 이용하여 구현
BFS(너비 우선 탐색)
- 그래프나 트리에서 너비를 우선적으로 탐색하는 알고리즘
- 시작점에서 가까운 노드부터 차례대로 탐색
참고
https://bedecked-operation-4d1.notion.site/99-4-TIL-DFS-BFS-1caeb405261e80ca84a8ecaef620f1ab
