[백준] Python - 안전 영역

2468번: 안전 영역

 

음식물 피하기와 마찬가지로 Flood Fill 알고리즘을 알아보고자 푼 문제다.

똑같이 별 다를 건 없고 BFS를 통해 해결했다.

 

이 문제의 경우 한 가지를 고려해야한다.

바로 강수량이다.

 

처음에 지역의 높이를 입력하면서 동시에 가장 높은 지역을 확인한다.

가장 높은 지역만큼 비가 온다면 그 높이를 초과하는 강수량은 확인할 필요가 없다.

따라서 비가 안오는 경우인 0부터 가장 높은 높이 -1 까지의 강수량을 가정하고 문제를 푼다.

 

예를 들어 가장 높은 곳의 높이가 9라면, 비가 9만큼 온다면 모두가 잠기게 되므로 안전지역이 0이니 고려할 필요가 없다.

비가 안온다면(=0) 모든 곳이 안전 지역이므로 1을 반환하면 된다

 

그 사이의 구간을 BFS를 반복해서 해결할 수 있었다.

 

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음