Problem Session 6 -5부

6-2 계속(1)

자 6-2번 다시 해봅시다

그림으로 이해하자

지난 시간에 말하길, 이렇게 했습니다. 사자가 있는 위치를 G, 각 거점을 L(Landmark), 거점을 잇는 길을 T, L과 L 사이에는 최대 5개의 T가 존재할 수 있으며, 각 T는 양의 정수의 길이를 가지고 있습니다. GPT의 도움을 받아 이를 그림으로 표현하면 다음과 같습니다. 노드 G, A, B, C, D, E와 각 노드를 잇는 Trail에 대한 내용은 아래와 같습니다.

노드와 노드 간 연결

여기서 Inside란 탈출해야 하는 바운더리 안쪽에 있는 것을 뜻하고 outside는 바운더리 밖에 있는 것을 뜻합니다. 아래 Trail은 각 노드 간 연결하는 Edge를 뜻합니다. 그럼 그림으로 표현하면 아래와 같습니다.

Weight의 표현 위치가 좀 이상하지만...

음... 다시 뽑아봅니다

훨씬 좋습니다. 

힌트 1 : 각 랜드 마크를 잇는 길은 5개다

문제의 조건은 Euclidean Disatance가 계속 늘어나면서도 바운더리를 탈출하는 알고리즘을 구현하는 것입니다. 거기에 O(N)이라는 조건이 들어있습니다. 지난 시간을 통해 몇몇 SSSP(Single Source Shortest Path) 알고리즘들이 O(|V|+|E|)의 조건을 가지는 것을 보았습니다. 주입식 교육의 한국인은 각각 어떤 것들이 그랬는지는 까먹었습니다. 그러나 조건에서 V와 E와의 상관관계를 볼 수 있습니다.

즉, 한 노드의 최대 Degree(편의상 in)는 5이라는 뜻이 됩니다. 따라서 O(|E|) = O(5|V|) = O(|V|)가 됩니다. 아 힌트하나 받았습니다. 그럼 이제 문제를 고민하고 풀어야 하는데...

다음 시간으로...