알고리즘 Floyd 과제

[Sabro98]

Floyd 파트 관련 과제 (난이도 순서)

필수
[1] [2]

위 문제들을 스터디 시간에 아래와 같은 토론을 진행하겠습니다.

1. 어떤 부분이 어려운지?
2. 어떻게 해결하는지?
3. 시간복잡도는?

스터디 전까지 모두 풀어와주세요!

스터디 시작 전까지 Issue에 자신만의 답을 남겨주세요!

만약 못풀겠으면, 구글에 검색하더라도 꼭! 풀어와주세요

톡방에 전달 부탁드립니다~

---

@tjdeo1102 @rkdbq @jys-jeong @bootkorea @tlstmdgjs

[joonas-yoon]

둘 다 재밌는 문제네요 ㅎㅎ 덕분에 재밌게 풀었습니다~ 👍

2번 문제는 다익스트라로 해보려했는데 잘 안됐네요 흑

[rkdbq]

[1]

1. 어떤 부분이 어려운지?

노드 사이의 최단 거리 뿐만 아니라 그 경로에서 방문하는 노드의 순서(가장 먼저 거쳐야 하는 노드)를 출력해야 한다는 점이 새로웠습니다.

2. 어떻게 해결하는지?

테이블에 최종 방문 노드 prev 노드를 두어 역추적해 해결했습니다. (e.g. table[i][j]라면 j 노드 방문 전 노드를 테이블에 같이 저장)

3. 시간복잡도는?

테이블을 채우는 데 O(N^3), 역추적 하는 데 O(N^3)의 시간복잡도를 가지므로 최종적으로 O(N^3)의 시간복잡도를 가집니다.

[2]

1. 어떤 부분이 어려운지?

최단 경로 이외의 경로를 어떻게 처리할지 떠올리기 어려웠습니다.
연소가 양쪽에서 진행되는 시점을 어떻게 처리할지 떠올리기 어려웠습니다.

2. 어떻게 해결하는지?

최단 경로 테이블 채우기, 최장 경로 테이블과의 거리 차이 계산하기, 시간 계산하기 세 단계로 나누어 접근했습니다.

3. 시간복잡도는?

테이블을 채우는 데 O(N^3), 어느 노드로부터 시작해야 하는 지 테스트하는 데 O(N^3)의 시간복잡도를 가지므로 최종적으로 O(N^3)의 시간복잡도를 가집니다.

[bootkorea]

[1]

어떤 부분이 어려운지?

플로이드-와샬 알고리즘을 이해하고 있다면 쉽게 해결할 수 있는 문제라고 생각함.

어떻게 해결하는지?

본인을 방문하는 경우를 제외한 나머지 케이스를 모두 2차원 배열에 저장하였고, 경로표 역할을 수행하는 2차원 배열을 활용하여 최종 출력 결과를 이끌어냄.

시간복잡도는?

모든 정점의 최단거리를 탐색하는 3중 for문을 반복하는 과정은 O(n^3)이며, 이것이 Dominant이므로 최종 시간 복잡도 역시 O(n^3).

[2]

어떤 부분이 어려운지?

양방향 그래프에서 Floyd-Warshall 적용까지는 괜찮았으나, 이를 활용하여 모든 간선이 소멸되는 시간을 유도하는 방법을 떠올리는 데 애를 먹음.

어떻게 해결하는지?

가중치가 L인 간선 M이 타는 데 걸리는 시간은 '((시작점 ~ M까지의 시간) + (도착점 ~ M까지의 시간) + 가중치 L) / 2' 로 결과를 유도하여 해결하였습니다.

시간복잡도는?

모든 정점의 최단거리를 탐색하는 3중 for문을 반복하는 과정은 O(n^3)이며, 이것이 Dominant이므로 최종 시간 복잡도 역시 O(n^3).

[tjdeo1102]

[1]

어떤 부분이 어려운지?
노드 간의 최단 거리에서
조금 더 나아가 최초 방문 노드까지 저장해주는 부분의 구현이 필요했습니다.

어떻게 해결하는지?

플로이드 알고리즘에 의해 새롭게 노드 간 최단 거리가 갱신 될 때마다 최초 방문 노드를 갱신해주는 작업으로 해결했고, 따라서, 최초 방문 노드를 저장해주는 배열을 필요해 의해 추가해주었습니다.

시간복잡도는?
플로이드 알고리즘 중에 최초 방문 노드 갱신 작업이 O(1)만큼 진행됩니다. 결국 플로이드 알고리즘 시간복잡도만을 생각해주면 되어서 O(n^3)의 시간복잡도를 가졌습니다.

[2]

어떤 부분이 어려운지?

노드 사이의 간선에서 최장 간선의 연소 시간을 구해줘야 하는 부분(두 노드 사이에 아직 연소 되지 않은 간선이 있는 경우)이 있었는데, 이 과정에서 남은 간선의 길이가 전부 연소하는 시간을 구하기가 어려웠습니다.

어떻게 해결하는지?

먼저, 임의의 경유 노드가 있고 시작 지점, 도착 지점의 노드, 총 3개의 노드가 있다고 할 때, 필요한 것은 임의의 경유 노드와 도착 노드 사이에서 발생하는 연소가 아직 안된 간선이 존재하는 경우에 걸리는 시간을 고려해줘야되고, 이는 두 노드 사이에 최장 간선에서 (시작도착),(시작경유) 두 최단 거리 시간의 차이 만큼의 시간에 따라 연소가 안된 간선 길이를 구해줄 수 있었고, 이를 이용해 시작지점과 도착지점 사이의 연소 시간을 구할 수 있었습니다. 그리고, 이러한 과정을 시작 노드만 바꾸어서 진행해주고, 그 중에서 가장 연소 시간이 짧은 것을 도출했습니다.

시간복잡도는?
최단 거리를 구하기 위해 플로이드알고리즘을 사용 O(n^3), 연소 시뮬레이터에서는 시작 노드의 경우는 n개가 있고 각 시작 노드 마다 경유 노드 (n개), 도착 노드 (n개)를 탐색하므로 총 O(n^3)의 시간복잡도를 가집니다. 그리고 플로이드와 시뮬레이터는 서로 독립적인 관계이므로 O(n^3)+O(n^3)=O(n^3)이 총 시간복잡도입니다.