[백준] 16118 달빛 여우

16118번: 달빛 여우

 

풀이 아이디어

 

다익스트라 문제로

늑대는 한번은 2배 빠른 속도 한번은 2배 느린속도로 이동

여우는 정상적인 속도로 이동하며

이때 여우가 늑대보다 빠르게 도착 할 수 있는 지점이 몇개인가를 찾는 문제이다.

 

가중치가 거리이기 때문에 2배 빠른 속도라는건 가중치를 2배로 나눈다는 것과 동치이다.

 

따라서 여우와 늑대가 시작지점에서 끝지점까지 갈 수 있는 모든 거리를 구한다음

서로를 비교하며 여우가 더 작은 값을 갖고 있는 지점을 카운트하면된다.

 

여우는 정석적인 다익스트라로 구하면 되고

늑대는 다익스트라를 조금 변형하여 이동횟수를 1과 0으로 기록하여

2배 빨라야 할 때 와 2배 느려야 할 때를 계산해서 가중치를 계산하고

이동횟수를 스위치 시킨다음 다시 큐에 넣어서 계산하면된다.

 

그리고 이동횟수에 따라서 가중치를 따로 저장해야 한다.

이 부분은 백준의 벽부수고 이동하기 처럼  한 지점에 2개이상의 값을

저장해야하는 유형과 유사하다.

 

또한 한바퀴 돌아서 이동횟수 홀짝을 엇갈리게 한 뒤 시작지점에서 출발하는게 답이 될 수 있으므로

시작지점도 다른 지점과 똑같이 처리해야한다.

 

위 방법이 다른 사람들이 많이 푼 방식이고

 

본인같은 경우

dfs보단 bfs느 낌이 먼저 들어서

2배 빠르게 계산하는 큐와  2배 느린 큐를 사용해서

한쪽 전부 비우고 다른 한쪽 전부 비우고를 반복하여

큐에 잔여가 없을 때까지 해서 풀었다.

 

 

시행 착오

 

최근에 정렬을 많이 사용하다 보니까 우선순위 큐의 디폴트 값이 내림차순이라는 것을 까먹고

시간초과의 근본적인 원인을 뒤로한채 다른 부분을 최적화 하려고 찾아봤다.

 

예를 들어

나눗셈 대신에 곱셈을 사용해서만 푼다던가..

 

결국에 우선순위큐가 문제라는 것을 찾았고 풀 수 있었다.

 

 

최적화 하기

 

일단 내가 풀었던 2개의 큐를 사용한 방식은 하나의 큐를 사용한 방법보다 비효율적 것이다.

우선순위 큐를 사용한 다익스트라는 O((V + E) log V)가 나오기 마련인데

큐를 두개로 나눠서 푸는 바람에 불필요한 계산까지 할 가능성이 농후하기 때문이다.

 

예를 들어서 가중치가 엄청큰 길이 존재한다면, 다익스트라는 그 길을 건너지 않지만,두개의 큐를 사용한다면, 반드시 건너게 된다.

 

즉. 유별나게 짧은 길이 하나만 존재한다면 위 아이디어보다는 오래 걸리게 될 것이다.

 

다만 노드의 사이즈가 큰 편은 아니라서 극악의 데이터케이스가 온다 한들 가망 없는 노선은 제거되어 최적화 되기 때문에 문제의 조건은 만족하는 것 같다.

 

벡터를 사용해서 입력값을 받았고 중복 경로에 대해서 예외처리했지만,

unordered_map을 사용하는 편이 조금은 더 빠를 것이라고 판단된다.