[Graph] Advanced LCA Algorithm

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc 

SW Expert Academy

 

[문제 요약]

1. BFS방법을 통해 Node를 방문한다 ex) 1 ->2->3->4

2. (1->2거리) + (2->3거리) + (3->4거리) + (4->1거리)

 

[ISSUE]

문제를 처음 읽고 BFS + LCA를 활용하면 되는 문제라 생각하고 신나게 문제를 풀었다.

그러나 시간초과가 발생해버렸다..

무엇이 문제일까 다시 생각을 해봤다.

 

BFS는 정형적인 패턴이니까 시간을 더 단축하긴 어려울것이라는 판단이 들었다.

LCA를 활용해 거리를 계산하는 부분에서, parent를 찾을때 까지 while문을 순회하는데 이부분이 마음에 걸렸다.

아니나 다를까, LCA Algorithm에 대해 조금만 더 찾아보니 Advanced알고리즘이 존재했고 이에 대해 정리해보고자 한다.

 

[Advanced LCA]

1. 시간 복잡도

   1) 기존방식 : O(N)

   2) 개선된 방식 : O(logN)

 

2. 방법

   1) 모든 노드에 대해 깊이와 2^i번째 부모에 대한 정보를 계산한다

   2) 두 노드의 깊이를 맞춘다

   3) LCA를 향해 거슬러 올라간다.

 

3. 시간복잡도 분석

   1) DP를 활용해 시간 복잡도를 개선할 수 있다

       (세그먼트 트리를 이용하는 방법도 존재합니다. -> 다음에 알아보자)

   2) 매 쿼리마다 O(logN)

 

기존에 부모를 찾아 올라갈때는 1칸씩 올라갔다면, 개선된 방법은 2^n칸 만큼 올라가는 방식을 활용한다.

이 부분이 처음에 직관적으로 와닿지 않았는데 예시를 보고 이해할 수 있었다.

만약 25칸을 올라가야하는 상황이라고 가정하자.

   1) 25칸 남음 (16 < 25 < 32) -> 16칸 점프 가능

   2) 9칸 남음 (8 < 9 < 16) -> 8칸 점프 가능

   3) 1칸 남음 -> 1칸 올라감

이렇게 3번의 연산과정을 통해, 25칸을 올라갈 수 있다.

따라서, 이 과정에서 시간 복잡도를 줄일 수 있다.

 

이렇게 2^n승으로 거슬러 올라가는 방법은 아래 두 상황에서 모두 사용할 수 있다.

1️⃣ 처음 두 노드간 depth를 맞출때

2️⃣ depth가 통일된 두 node가 같이 parent를 찾아 나갈 때

 

다만 공간복잡도가 늘어나기에 trade off가 발생한다.

기존에 1차원이던 parent배열은 2^n칸 앞에 있는 부모의 정보를 저장해야 하므로 2차원이 된다.

공간복잡도는 N에서 NlogN이 된다.

 

Advanced LCA는 아래 영상을 참고했다.

https://youtu.be/O895NbxirM8?t=284 

 

[추가적으로 알게된것]

1. 최단거리와 최소비용을 구분할것.

처음에 문제를 읽고, 최단거리를 구해야한다는 생각이 들었다.
최단거리는 다익스트라..? 하는 생각이 머리속에 제일 먼저 스쳐 지나갔다.

이건 내가 공부를 야무지게 하지 않아서 발생한 생각이다..

다익스트라와 플로이드 워셜 알고리즘은 최소'비용'을 구할 때 사용하는 알고리즘임을 기억해두자.

 

다익스트라는 (1)Graph에서 (2)edge에 weight가 존재하는 경우 사용한다.

tree도 graph의 일환이고, tree에서의 weight를 1로 설정한다면 다익스트라를 활용할수도 있을것이다.

다만, 다익스트라 알고리즘은 시작정점이 고정된 상태에서의 SP를 구하는 것이다.

따라서, 시작정점이 매번 바뀌는 본 문제에 적합하지 않다.

참고로 Priority Queue를 활용한 다익스트라의 시간복잡도는 O(nlogn)이다. (그냥하면 O(n^2))

 

그렇다면 임의의 정점에서의 거리를 모두 구할 수 있는 플로이드 워셜 알고리즘은 어떤가.

플로이드워셜은 시작노드를 1~n으로 두고, 각각에 대해 최단경로를 구하는 알고리즘이다.

시간복잡도는 O(n^3)이다.

 

2. Tree에서의 최단거리는 BFS만 있는것이 아니다.

하나하나 방문하는 BFS보다 LCA가 효율적이다는 생각은 자명하다.

아래는 이와 관련해 참고한 글이다.

트리에서 최단 경로를 구하기 위한 또 다른 방법?