tksgo2582   5년 전

예제 코드들은 답이 되는데 이 코드가 틀린 이유를 잘 모르겠어요 ㅠㅠ 도 와주세요 고수님들~~

djm03178   5년 전

함수 이름을 dfs라고 지어놓고 dfs를 하지 않기 때문입니다.

경로 업데이트를 임의의 횟수만큼 한다고 해서 최종적으로 도달이 가능한지를 알 수 있을까요?

아래 예시에서 1번 정점에서 2번 정점으로는 도달이 가능하지만 이 코드는 가능하지 않다고 출력합니다.

tksgo2582   5년 전

밑에서 업데이트 된게 위에서는 적용이 안된다고 생각해서 그렇게 했었는데 

그럼 정점의 수만큼 반복을 한다면 어떨까여?? 이렇게 하면 dfs가 아니라 어떤 알고리즘이 되는거죠???

답변 정말 감사합니다~1!!

djm03178   5년 전

정점의 수만큼 반복한다면 플로이드 와샬 알고리즘의 원리가 되는 건데 이 코드가 정확히 그걸 구현하는 건지는 모르겠네요. 플로이드 와샬이라면 한 번만 돌리는 것으로 전체 그래프에 대한 답을 구할 수 있습니다.

tksgo2582   5년 전

이런식으로 고쳐서 맞긴 했는데 이 알고리즘은 효율적이지 못한건가요?? 플로이드와샬 알고리즘에 대해서는 공부를 해봐야 겠네요

djm03178   5년 전

복잡도가 O(N^4)이니까 효율적이진 않습니다. 그냥 제대로 DFS를 수행하면 O(N^3)입니다.

tksgo2582   5년 전

답변 감사합니다!! 다시 한번 해볼게요!!

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