DFS_안전 영역_백준 2468번
-문제-
-문제 접근-
어떤 높이 이상인 지역이 몇 개의 안전한 영역으로 나눠지는지 찾는 문제이며 BFS/DFS를 활용하여 연결된 영역 갯수 찾는 문제입니다. 저는 DFS로 풀었으며 높이(강우량)에 따른 안전한 영역의 최대 개수를 찾는 것이 키 포인트입니다.
1. 최대 높이 설정
2. 각 높이(강우량)에 대해 안전 영역 갯수 찾기.
3.모든 높이(강우량)에 대해 최대 안전 영역 갯수를 갱신하면서 찾기.
한마디로 모든 높이에 따른 안전 영역 갯수를 비교하고 갱신하여 최대 안전 영역 개수를 찾으면 됩니다.
-전체 코드-
-코드 설명-
위에 dx, dy는 상하좌우 이동을 하기 위해서 사용하였으며 x를 열, y를 행으로 생각하시면 이해하시기 편하실 겁니다.
그렇게 하여서 dx가 -1, 1인 경우 열을 의미하여서 상, 하를 의미하게 되고 마찬가지로 dy는 좌, 우를 의미하게 됩니다.
dfs의 인자는 x,y,h를 받으며 시작하는 현재 위치에 방문했음을 표시하고 현재 위치를 기준으로 상하좌우 탐색을 하게 되며
인접한 노드들 중 범위안에 있는 좌표를 가지고 방문이 되지 않은 좌표 AND h보다 큰 값을 가진( 즉 물에 잠기지 않은) 조건에 부합한 좌표로 재귀적으로 동작을 하게 됩니다.
재귀적으로 동작을 함으로써 물에 잠기지 않은 인접한 안전 구역들이 다 탐색이 됩니다.
메인을 보면 입력 받게되는 크기에 맞춰서 map을 설정을 해줍니다.
여기서 max_h(최대 높이)를 찾아야 되는데 그 이유로는 이 문제에서 강수량(h)을 0부터 최대까지 변화하면서 찾기 위해서 최대 높이가 필요합니다.
이중 포문으로 입력 된 높이 중 가장 큰 값을 max를 사용하여 찾아서 넣습니다.
그 후 우리가 구해야되는 최대 안전 영역의 개수를 선언하여 주고 강우량을 0부터 아까 구한 최대 높이까지 for문을 돌려서 탐색을 합니다. 이 문제는 강수량에 따른 최대 안전 영역 갯수를 구하는 문제이므로 높이에 따라서 구하여야 해서
h가 변환할 때 마다 방문 배열을 초기화 해주어야 합니다.
max_safe_zone을 갱신 시켜줄 변수가 필요하므로 zone_count를 선언하여주고 이중 for문과 조건에 맞춰서 dfs를 실행하여 안전영역의 개수를 zone_count에 카운팅 해줍니다.
그리고 max_safe_zone의 값과 zone_count 값을 비교하여서 최대 안전 영역의 갯수를 갱신해줍니다.
위에 for문은 한마디로 강우량에 따른 최대 안전 영역의 개수를 갱신하여서 찾는다 라고 보시면 됩니다.
-END-
