백준 15972 물탱크

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

15972번: 물탱크

 

2018년 당시 서브태스크만 긁었던 문제. 당시에 생각한 아이디어 자체는 맞았기에 쉽게 AC를 받을 수 있었다. 

 

어느 한 칸의 물의 높이가 정해졌다고 생각하면, 그 칸보다 높은 인접한 칸을 따져 줄 때 크게 세 가지 경우가 있을 것이다. 두 칸 사이에 인접한 칸의 현재 상태보다 낮은 구멍이 없거나, 구멍이 두 칸의 높이 사이에 있거나, 구멍이 주어진 칸의 높이보다 낮은 경우이다. 첫번째 경우는 업데이트를 하지 않으면 되고, 두 번째 칸의 경우는 구멍의 높이로 업데이트 해주고, 세번째 경우는 주어진 높이로 업데이트하면 된다. 

 

높이가 낮은 순서대로 우선순위 큐에 넣어 따져 줄 칸을 정할 수 있고, 다익스트라랑 비슷한 아이디어이므로 이렇게 관리하면 된다는 증명도 비슷하게 할 수 있다. 

 

거리 대신 물의 높이를 기준으로 다익스트라를 구현하고, dis[i]+d[i][j]를 쓰는 대신 max(h[i], d[i][j])로 업데이트를 해 주면 쉽게 AC를 받을 수 있다.