(JAVA) 백준 16118번 : 달빛 여우 --- [다익스트라]

www.acmicpc.net/problem/16118

16118번: 달빛 여우

 

난이도 극악..

 

다익스트라 알고리즘 문제 중 거의 상급 문제..

 

주말 하루를 날리게 만든 문제입니다.

 

 

 

시간 제한이 1초이기 때문에 정말 어려운데요.

 

하..

 

아무튼 두 지점 사이에 가중치가 1이 아니기 때문에 BFS/DFS 는 사용할 수 없기 때문에

 

다익스트라 두 가지를 사용하면 되는데,

 

하나는 달빛 여우가 각 지점 별 최소 이동 시간을 구하기 위한 다익스트라 알고리즘

나머지는 달빛 늑대가 각 지점 별 최소 이동 시간을 구하기 위한 다익스트라 알고리즘

 

입니다.

 

 

달빛 여우야, 그냥 다익스트라 돌리면 되니 그냥 해결할 수 있는데 (이 때, 방문 체크 하지 않아야 해용!)

 

문제는 달빛 늑대의 다익스트라 알고리즘.

 

 

달빛 늑대는 홀수 번 째 이동할 때에는 이동 시간의 절반, 짝수 번 째 이동할 때에는 이동 시간의 두 배가 걸립니다.

 

 

각설하고, 자바에서 정답을 맞추기 위해 짚고 넘어갈 부분을 알아보겠습니다.

이부분만 이해한다면, 정답 쌉가능할 겁니다.

 

 

유의사항

---

  -  달빛 늑대 이동할 때 만약 3의 거리가 있다면, /2의 결과값은 1.5 입니다.

즉, 소수가 나와버리게 되면 계산에 있어서 더 느리고, 자료형도 double로 바꾸고..

이런 번거로운 문제점들이 있기 때문에 그래프를 그릴 때 *2 를 하여 거리의 값을 전부 짝수로 만들어버립니다.

 

 

  -  달빛여우와 달빛늑대 모두 해당하는 부분입니다.

아래 소스코드는 다익스트라 알고리즘 내부 예외처리 조건문인데요.

 

주석에도 적혀있듯이

 

"현재 지점까지 이동하는데 걸린 최소시간(다익스트라를 통해 얻은 최소시간) 보다 현재 해당 지점에 오기까지 걸린 최소시간이 더 크다면 CONTINUE 합니다."

 

이미 지금 도착했을 때의 걸린 시간보다 짧은 시간으로 이 지점을 왔던 적이 있기 때문에 굳이 지금 최소 시간가지고 체크할 필요가 없습니다. 그래서 바로 통과시키면서 실행시간을 절약할 수 있죠.

if(wolfTime[endVertex.state][end] < nowTime) {	// 현재 지점까지 걸리는 최소시간보다 현재 늑대가 해당 지점에 오기까지 걸린 시간이 크면 굳이 계산할 필요가 없다.
	continue;
}

 

  -  달빛늑대의 다익스트라 경우 현재 지점까지 느리게 걸어서 온 경우(1) 와 현재 지점까지 빠르게 달려서 온 경우(2). 총 2가지 경우가 존재하기 때문에 이를 구분해야해서 long[2][N + 1] 의 2차원 배열을 만들어 이동최소시간을 담습니다.

이를 위해 state int 변수를 만들어 0 / 1 flag 처럼 활용합니다.

 

  ***  참고로, 최소 시간을 계산하다가 int의 범위를 초과할 수 있기 때문에 long을 활용합니다.

  ***  또한, [N + 1][2] 대신에 [2][N + 1] 로 만들어서 MAX_VALUE 초기화를 더욱 빠르게 합니다. 이를 통해 시간 절약도 가능합니다.

 

 

 

  -  달빛여우의 다익스트라 알고리즘 경우 지점 방문여부를 체크할 필요는 없습니다.

단지, 처음 시작점의 이동최소시간 배열 값은 0으로 초기화는 해야하죠.

 

하지만, 달빛늑대의 경우 처음 시작점에서 시작해서 무조건 빠르게 달려야 하기 때문에 처음 시작점의 이동최소시간 배열 값 중 현재 지점까지 느리게 걸어서 온 경우 만 0으로 초기화를 해줍니다.

 

왜냐하면, 한 바퀴를 돌아서 처음 시작점을 경유했을 때 더 빠른 경우가 있기 때문입니다. (예외)

 

 

ex) 한 바퀴를 돌아서 처음 시작점을 경유했을 때 더 빠른 경우

 

5 5

1 2 1

1 4 5

4 5 4

5 1 3

2 3 450

 

답 : 0

 

 

 

  -  우선순위 큐를 사용하여 동작시간을 줄입니다. 최소이동시간부터 알고리즘 처리를 하면 최대한 continue로 넘겨버릴 수 있습니다.

 

 

 

 

이상입니다.

 

더 궁금하신 사항이나 질문

그리고 감사합니다! 라는 댓글

부탁드립니다.

 

 

감사합니다!

 

 

소스코드

---