풀이방법: 다익스트라
특정한 장소에 최단시간으로 모두 갔다오고, 그 중 가장 오랜시간 걸린 사람을 찾는 문제이다.
풀이방식
문제를 읽고 두 가지 풀이가 생각났다.
1.플로이드
2.다익스트라
처음에는 플로이드로 하면 금방할 것 같아 했는데 , 뭔가 오류가난다. 시간이 초과되고 그러는것 같다.
그래서 플로이드의 조건을 바꾸느냐? 아니면 다익스트라로 다시푸느냐...
다시하는게 빠를것 같아 다익스트라로 풀었다.
그냥 다익스타로 하기전에 고민을 좀 더 해봤다.
다시 생각해보면 우리는 X의 지점만 왓다리 갓다리 하면된다.
문제에서 보면 1 -> 2 가 4인데 이것을 뒤집으면 2 -> 1이된다. 보기에는 다르겠지만 의미는 같다.
따라서 두 가지의 방식을 사용하면된다.
일반적인 거리배열을 이용한것과 위처럼 뒤집은 배열을 사용한것 이 결과 두개를 더하면된다.
또한 우리는 기준이 되는 점을 알고 있기 때문에 기준점을 활용한다.
dist[i] = map{x}{i} + d[x]를 점화식으로 세운다.
나머지는 다른 다익스트라와 같다. (우선순위 큐쓰고,, 넣고 와일문 돌리고등.)
함수의 매개변수를 (int x, int{}{}map, int{} dist) 이렇게 받아주고 계산하면된다.(쓴 이유는 아래에 있다)
그리고 우리는 함수를 2번 호출한다. 왜냐하면 우리는 2개씩 배열을 만들것이기 떄문!
안뒤집은 배열, 뒤집은 배열, 안뒤집은 거리, 뒤집은 거리 이렇게 4개를 활용한ㄷ.
뒤집은 것을 넣게되면 아까 말한것처럼 1->2 를 2->1로 계산할 수 있다.
출력할때는
제일 큰 dist[i] + redist[i] 하면된다. 모두 x까지 왕복한 거리들이기 떄문이다.
코드 전체 보기
: 풀다가 잣다.. 어려웡.
'알고리즘(추가예정) > 다익스트라' 카테고리의 다른 글
| 백준 2665 미로만들기 (0) | 2017.10.30 |
|---|