16118번: 달빛 여우 풀이 아이디어 다익스트라 문제로늑대는 한번은 2배 빠른 속도 한번은 2배 느린속도로 이동여우는 정상적인 속도로 이동하며이때 여우가 늑대보다 빠르게 도착 할 수 있는 지점이 몇개인가를 찾는 문제이다. 가중치가 거리이기 때문에 2배 빠른 속도라는건 가중치를 2배로 나눈다는 것과 동치이다. 따라서 여우와 늑대가 시작지점에서 끝지점까지 갈 수 있는 모든 거리를 구한다음서로를 비교하며 여우가 더 작은 값을 갖고 있는 지점을 카운트하면된다. 여우는 정석적인 다익스트라로 구하면 되고늑대는 다익스트라를 조금 변형하여 이동횟수를 1과 0으로 기록하여2배 빨라야 할 때 와 2배 느려야 할 때를 계산해서 가중치를 계산하고이동횟수를 스위치 시킨다음 다시 큐에 넣어서 계산하면된다. 그리고 이동횟수에 따..
