[수업]물탱크(Greedy 문제)

Intro..

이 문제는 Greedy(탐욕) 관련 문제이다.

Greedy(탐욕) 관련해서 정리해둔 게시글이 있기 때문에 참고할 것.

문제

풀이

물은 특성상 젤낮은 구멍(높이 젤낮은)에 빠지는건 당연한 원리
=> 탱크 내부가 아무리 높이가 낮은 0이여도 젤 외곽의 구멍 높이에 따라 물이 빠지는건 너무 당연.

최외곽의 경우 젤 낮은 구멍은 위의 원리 그대로 적용 가능 -> 시작 지점.

만약 적용했으면 그 부분 물탱크는 없다고 생각하고 다음 케이스를 생각.
다음꺼도 최외곽에서 젤 낮은 구멍을..! 그이후 또 물탱크 없다고 생각하고 다음 케이스 생각.

…반복

그러다가 2가지 경우가 있음.
인접 물높이와 현재 구멍이 더 높거나, 작은경우. 이 케이스도 하면 끝

참고로 최소 물높이를 구하는것이므로 물탱크 벽 4방향에 구멍들 여러개면, 전부 확인해봐야 정확한 최소 물높이를 구할 수 있음

결론은 최외각의 젤 낮은 구멍에서 야금야금 찾아가는 방식

• 다익스트라 알고리즘의 최소 거리 구하는것 처럼, 최소 높이를 찾아가는 형태
  이를 배열이 아닌 우선순위 큐를 활용해서 해결했음(복잡도 더 좋음)

• 우선순위 큐는 최외곽 구멍들로만 구성이 되고, 최소 높이로 우선순위를 정해서 pop으로 사용하는 구조로 이해할 수 있다.

자세한 흐름은 아래 그림을 보고 참고

• 그림에서 물탱크 인접했을때 특징 2가지만 이해된다면 아래 식인 max(..,..) 가 유도 가능
• 또한, 예시처럼 최외각의 낮은 구멍을 선택해가면서 인접의 경우를 처리하면 답을 구할 수 있따.