Search

BOJ 2468 안전 영역

태그
그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색
브루트포스 알고리즘
생성일
2024/12/11 12:13

문제 설명

•
장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 구하는 문제

예제 입력/출력

•
입력1
5 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7
Plain Text
복사
•
출력1
5
Plain Text
복사

제약 조건

•
1≤N≤1001 ≤ N ≤ 100
◦
NN: 가로(세로)의 길이
•
1≤H≤1001 ≤ H ≤ 100
◦
HH: 어떤 지역의 높이

문제 풀이

•
브루트 포스 + 그래프 탐색을 이용하여 문제를 해결하면 된다. - O(100⋅N2)O(100 \cdot N^2)
◦
노드의 최대 개수가 N2N^2이고, 나올 수 있는 간선의 최대 개수는 4N24N^2
◦
어떤 지역의 높이의 최대값은 100
▪
즉, 최악의 경우 O(100⋅5N2)O(100 \cdot 5N^2)
모든 높이에 대해 살펴보며, 각 높이마다 안전한 영역의 개수를 그래프 탐색을 이용해서 구한다.

풀이 코드

DFS 풀이
BFS 풀이