6006 - Problem session 5
그래프를 이해하자
오늘도 돌아왔습니다. 6006에는 Problem session과 Problem set이 있습니다. 전자는 문제를 직접 풀어주는 시간이고, 후자는 숙제입니다. 전자의 수업을 들어도 이해가 안 갈 수 있습니다. 바로 저처럼. 글을 읽어보고 직접 써보며 이해해 봅니다. 저도 제가 이해가 어느 정도 되는 부분들을 설명해 보며 이야기해보도록 하겠습니다.
5-2 Internet Inestiation
우선 문제가 무엇일까요. 영어를 읽으니 좀처럼 이해가 잘 가지 않습니다. 수업도 들어보고 글도 읽어봤습니다. 그러고 난 후 문제가 이해가 되었습니다. 문제는 이렇습니다.
조건
- 와이파이 네트워크가 있다고 가정함
- 와이파이 네트워크를 위해 r 개의 router가 존재하며 이 중 일부는 entry point로 지정됨
- 몇몇 router들은 서로 양방향 와이어(w_i)로 연결되어 있음
- 각 양방향 와이어(w_i)의 길이는 l_i로 표현. 이때 l_i는 양의 정수 => undirected
- 각 router의 latency는 자신과 가장 가까운 entry point거리까지 비례함
- 모든 거리의 합(Sum(l_i))은 최대 100r 보다 작거나 같습니다
문제
모든 router, 다시 말하면 일반 router와 entry point의 latency의 합을 구하는 알고리즘 중 O(r)이 되는 알고리즘을 설명하는 것입니다. 이 문제를 그림으로 표현해 보면 아래와 같습니다.
문제는 한 장으로 표현하면 이렇다이 정도로 도식화되었다면 이제 이해가 될 것입니다. 원칙대로라면 구분을 위해 각 R과 L에 대해 번호를 써야 하지만 편의상 무시했습니다. 자 그럼 이 문제는 어떻게 풀까요? 차근차근해나가도록 합니다.
아이디어
정말 아무것도 모르는 상태에서 난감한 문제입니다. 왜냐하면, 진도상 배운 최단거리 알고리즘은 BFS와 DAG Relaxation이 끝인 상태입니다. 다시 말하면 BFS와 DAG Relaxation만 아는 상태에서 문제를 푼다고 보면 됩니다. 조건에서 위 그래프는 undirected이기 때문에, 소거법에 의해 BFS밖에 쓸게 없습니다. 근데 또 문제가 생깁니다. BFS는 unweighted인 경우에만 쓰인다는 것입니다.
그럼 이런 아이디어를 생각할 수 있습니다. weighted 그래프를 unweighted로 바꾸면 되지 않을까? 이 접근이 맞습니다. 왜냐하면 조건에서 Sum(l_i)=100r이라고 주어졌기 때문입니다. 자 그럼 이게 왜 맞는지 하나하나 해나 가보면 됩니다.
1. weighted graph=> chainged graph
조건에서 두 노드 간 거리는 양의 정수라고 했습니다. 좋은 일입니다. 그렇다면 BFS사용을 위해 두 노드를 양의 정수의 체인으로 바꿀 수 있습니다. 가령 노드 두 개 사이 거리가 4였다면, 3개의 노드를 추가하고 4개의 거리 1의 선으로 치환하면 됩니다. 그림으로 보면 아래와 같습니다.
이런 길이 l의 노드 앳지가 있었다면
이렇게 바꿉니다우리가 신경 쓰는 것은 time complexity입니다. 그럼 위 작업을 모든 노드에 대해서 하면 어떻게 될까요? 각 edge의 time complexity는 l_i입니다. 그리고 주어진 조건에서 Sum(l_i)=100r이라고 했습니다. 따라서 위 작업의 time complexity는 O(r)입니다.
2. BFS를 해야 하는데...
근데 여기서 문제가 생깁니다. BFS를 쓰려면 시작 노드가 있어야 합니다. 근데 위 그림에서 본 현재 네트워크 구조로는 O(r^2)의 알고리즘을 짜게 생겼습니다. 쉽게 이렇게 얘기해 보도록 하겠습니다. 만약 전체 네트워크 중 반이 entry point라면 모든 entry point에 대해 BFS를 해야 합니다. 각 BFS는 O(|V|+|E|)이지만, 이 문제에서 V=r, E= 100r이었기 때문에 O(|V|+|E|) = O(r/2+50r) = O(r)이 됩니다. 이 O(r)을 2/r 동안 반복하게 되니 O(r^2)가 됩니다.
그럼 어떻게 해야 할까요? 여기서는 super node(이하 S)라는 개념을 도입합니다.
Super Node 도입 후사실 좀 신기한 부분이기도 한데 S를 도입해서 모든 문제를 해결할 수 있습니다. 우선 설명을 한번 보시죠. entry에 대해 loop를 하는 대신 S에서 BFS를 수행합니다. 그러면 각 router의 가장 가까운 router까지의 거리는 어떻게 될까요? 바로 Super Node를 기준으로 계산한 값에 -1을 하면 됩니다. 이 부분을 좀 더 곱씹어 보고 이해가 됐다면 다음으로 넘어갑니다. 그럼 위 상태의 time complexity는 어떻게 될까요. BFS를 적용할 수 있으니, router와 edge의 수만 구하면 됩니다.
1. 노드의 수는 super node까지 r+100r(체이닝) + 1개가 되었습니다.
2. Edge의 수는 100r +r(Entry Point의 최대 수)이 되었습니다
따라서, O(r+100r + 100r +r) = O(r)이 됩니다. 그럼 최종 time complexity는 chained graph O(r)과 BFS O(r)을 더해 O(r)이 됩니다. 휴우 힘들었다.
