CHULMING   4년 전

일단 플로이드 알고리즘을 사용해서 풀긴했는데,

처음에 풀 때 힙을 사용한 다익스트라 알고리즘을 이용해서

S(시작) -> E(도착)  + E -> S 작업을 정점 수 만큼 반복하고,

그중 최댓값을 갱신해주는 방향으로 풀었는데 시간초과를 받았습니다.

결국 다익스트라(n2) 을 n번 반복하니 n3 꼴이 되버리게 되더군요.


Q.1)

플로이드도 n3이니까 1000의 인풋에 대해서는 둘 다 시간초과가 나야되는 것 아닌가요 ?

알고리즘 배울때 같은 n3 이더라도 플로이드가 더 빠르다고 들었는데 그 차이 인건가요..


Q.2)

1000이라는 인풋에 대해 플로이드 알고리즘이 시간초과가 안나온 이유가 뭘까요?



혹시 몰라서 제가 사용한 다익스트라를 첨부 해보겠습니다..




sgchoi5   4년 전

저도 N 이 1000 이라 플로이드로 풀고, 같은 고민이.. 혹시, 답을 얻으신게 있으신가요?

http://gooddaytocode.blogspot.... 에 가시면 문제 출처 대회에서 제공하는 TC 와 정답을 보실 수 있습니다.

정답 예제 코드는 다익스트라 썼네요.. 한 번 보시면 될 듯 하고,

TC 도 보니까 1000 개 짜리가 있던데, 왜 시간 초과 없이 잘 될까요? 음..

skim451   4년 전

늦게나마 댓글 남겨봅니다.

V = 정점의 갯수 

E = 간선의 갯수 

T = 목적지 (파티가 열리는 곳)

라고 했을 때, 

결론부터 얘기하자면 다익스트라를 V번 반복하지 않아도 이 문제를 풀 수 있습니다. 

방법은 다음과 같습니다. 

1) T를 출발 노드로 하여 다익스트라 알고리즘을 돌립니다. 

알고리즘이 끝나면 T에서 출발해서 다른 노드로 가는 최단경로를 모두 구하게 됩니다. 

그럼 이제 임의의 노드 x에서 출발해서 T로 오는 거리만 찾으면 답을 구할 수 있겠죠. 

2) x -> T 거리를 구하기 위해선 출발노드 x가 매번 다르기 때문에 다익스트라를 n번 반복해야 하는 것으로 보입니다. 

하지만 이런 방법도 있죠. 그래프 간선방향을 거꾸로 뒤집습니다. (e.g. 1->3이 5걸리면 3->1이 5 걸리는 것으로 변경)   

그리고 T 노드를 출발 노드로 하여 다익스트라를 돌리면 x -> T 의 거리를 모두 구할 수 있습니다.

3) 1, 2 에서 구한 거리를 더해서 가장 큰 값을 찾으면 되겠죠 ㅎㅎ


이렇게 O(|E| + |V| log |V|) 만에 문제를 풀 수 있네용.

플로이드 워셜은 O(|V|3) 의 정말 무거운 알고리즘이기 때문에 정말 필요한 경우가 아니면 피하셔야 합니다.

akrja4   3년 전

정점방향 바꾸는시간+다익스트라

O(|E|+|E|log|V|) 아닌가요?

댓글을 작성하려면 로그인해야 합니다.