11403번 - 경로 찾기
예제 코드들은 답이 되는데 이 코드가 틀린 이유를 잘 모르겠어요 ㅠㅠ 도 와주세요 고수님들~~
함수 이름을 dfs라고 지어놓고 dfs를 하지 않기 때문입니다.
경로 업데이트를 임의의 횟수만큼 한다고 해서 최종적으로 도달이 가능한지를 알 수 있을까요?
아래 예시에서 1번 정점에서 2번 정점으로는 도달이 가능하지만 이 코드는 가능하지 않다고 출력합니다.
밑에서 업데이트 된게 위에서는 적용이 안된다고 생각해서 그렇게 했었는데
그럼 정점의 수만큼 반복을 한다면 어떨까여?? 이렇게 하면 dfs가 아니라 어떤 알고리즘이 되는거죠???
답변 정말 감사합니다~1!!
정점의 수만큼 반복한다면 플로이드 와샬 알고리즘의 원리가 되는 건데 이 코드가 정확히 그걸 구현하는 건지는 모르겠네요. 플로이드 와샬이라면 한 번만 돌리는 것으로 전체 그래프에 대한 답을 구할 수 있습니다.
이런식으로 고쳐서 맞긴 했는데 이 알고리즘은 효율적이지 못한건가요?? 플로이드와샬 알고리즘에 대해서는 공부를 해봐야 겠네요
복잡도가 O(N^4)이니까 효율적이진 않습니다. 그냥 제대로 DFS를 수행하면 O(N^3)입니다.
답변 감사합니다!! 다시 한번 해볼게요!!
댓글을 작성하려면 로그인해야 합니다.
tksgo2582 5년 전
예제 코드들은 답이 되는데 이 코드가 틀린 이유를 잘 모르겠어요 ㅠㅠ 도 와주세요 고수님들~~