A. 문제설명
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 �
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 아래와 같은 N*N 크기의 땅이 존재
2. 각 땅에는 높이 값이 주어지고, 이제 해당 지역에 비를 뿌리려고 함
3. 비가 내릴 때, 다음과 같이 특정 높이 이하의 지역들은 물에 잠기는데 이때 물에 잠기지 않은 인접한 지역들을 모아 안전 영역이라고 함
4. 강수량에 따라 특정 높이로 물에 잠기는 지역이 달라질 수 있을 때 최대가 되는 안전 영역의 갯수를 구하라
B. 접근법
BFS
이 문제는 간단한 BFS 적용으로 해결할 수 있었다. 다만 BFS 적용시 실수로 엔트리를 POP한 이후에 방문체크를 하는 방식으로 처음 구현하여 메모리 초과가 발생하였었다. 이 경우, 인접한 4개 방향을 탐사하며 큐에 넣는 동안 자기 차례의 큐의 엔트리가 방문체크를 하지 않기 때문에 중복 탐사가 발생하였다. BFS는 무조건 큐에 삽입 이전 방문체크를 해주어야 한다.
C. 풀이
1. 물에 잠기는 영역 높이를 각각 배열내 최대 최소 값부터 반복하며 안전영역을 탐사
2. BFS 큐는 인접한 영역 중 안전영역을 탐사
3. 한번의 안전 영역을 찾을때마다 cnt를 증가
4. 매 높이의 안전 영역수 계수완료시 전체 최대값에 업데이트
D. 내 코드
