Problem Session 6 -4부

6-2

이제 알았는데, 해당 세션은 녹화된 비디오가 없더군요. 좋습니다. 강하게 키우는 나 자신

문제이해하기

문제는 라이온 킹 그런 걸 형상화한 것으로 보입니다. Bisma라는 암사자가 있고, Honor stone에서 탈출하는 방법을 구하는 것입니다. 현재 Bisma가 있는 곳을 gorge(G)라 하고, 닿을 수 있는 곳들을 Landmark(L)이라고 표시합니다. 그리고 각 L은 Trail(T)로 연결되어 있습니다. 각 L끼리는 최대 5개의 T로 연결되어 있습니다. 각 T는 양의 정수의 길이를 가집니다. L 중 일부는 Honor stone 안에 있고, 일부는 밖에 있습니다.

Never Return의 조건은 a라는 L(L_a), b라는 L(L_b)가 있을 때, G를 기준으로 거리(Distance, D)를 기준으로 조건을 만족해야 Never Return이 됩니다. 가령, a에서 b로 이동하려 할 때 D(G, L_a)가 D(G, L_b) 보다 명확히 작아야(부등호 < 를 뜻하는 듯) Never Return을 충족합니다. 여기서 거리는 직선거리(유클리디언 거리)입니다.

이 제약조건 안에서 O(n)(n은 L의 개수)으로 Honor stone을 탈출하며 최단거리로 Never return을 구현하는 알고리즘을 설명하면 됩니다.

힌트 : DAG?

일단 생각하다가 막막해 GPT에 물어보니 DAG를 구성해 보라 합니다. 하지만 제가 문제를 제대로 읽었다면, 구간 중 일부는 loop를 구성할 텐데 이게 될지 모르겠습니다.