[일반] 이 문제 보고 어떤 알고리즘 써야할지 갈피 잡히냐?

[익명(221.163)]

https://www.acmicpc.net/problem/15730

바로 이 문제임. 

너비 우선 탐색으로 시뮬 돌리는 건줄 알았는데 개같이 털려서 힌트 좀 검색했는데 무려 '다익스트라'로 푸는 거더라..

물론 너비 우선 탐색도 되긴 하겠지만 다익으로 하는 게 더 쉬움.

어떻게 이 문제를 보고 다익으로 할 생각을 하냐?

이런 건 짬이 해결해주는 거임?

[익명(223.33)]

어케 다익으로 푸는거임?

[익명(221.163)]

max(현재 좌표에서 물을 채웠을 때의 높이의 최솟값, 다음 좌표의 높이) < 다음 좌표에서 물을 채웠을 때의 높이의 최솟값 -> 갱신 후 pq에 push 하는 식으로 풀 수 있음.

[익명(49.168)]

어떤 칸에 물이 h만큼 차있을 조건을 생각해봐

[익명(58.230)]

유니온 파인드로는 못푸나? 해봐야지

[익명(211.246)]

이거 물탱크 하위호환 아님?

[익명(211.246)]

https://www.acmicpc.net/problem/15972

[익명(220.127)]

플래 다익스트라 어려운 거 많더라