[이경훈]

안녕하세요. 4-5번 문제 이해가 잘 되지 않아 질문드립니다.

x라는 보물 상자를 열 수 있는 열쇠모양의 조건이 '현재 위치에서 x를 열어줄 열쇠 모양'라고 되어있는데, 이것이 보물상자가 없이 갈림길이나 안내판이 있는 곳에서 '보물상자마다 필요한 열쇠의 모양'과 무슨 관련이 있는 것인지 이해하지 못했습니다.

안내판과 갈림길에서 필요한 열쇠의 모양은 이후에 이어지는 길들(자신의 자식 노드 및 그 자손 노드들)에 의해 결정된다고 생각했는데, 이러면 leaf에 있는 보물상자는 누가 결정하는 건가요?

감사합니다.

[shkim]

우선 안내판, 갈림길이 암시하는 열쇠는 보물상자에서 사용되는 열쇠가 아닙니다. 각각 안내판과 갈림길 자체에 대한 정보라고 생각해주세요.

간단한 예로 알림판 [x]x 를 보겠습니다(알림판 [x]e1 에서 e1=x인 경우입니다).
x의 열쇠가 α이고 e1(=x)의 열쇠모양이 β일때 [x]e1 (=[x]x)의 열쇠모양은 (α, β) 입니다. 하지만 x=e1이기 때문에 열쇠모양 α=β 이고, 알림판 [x]x의 열쇠모양은 (α, α) 혹은 (β, β) 입니다. 이 모양을 만족하는 알림판의 최소크기 열쇠는 (-,-) 가 될 것입니다. 하지만 우리가 필요한 열쇠모양은 알림판이 아닌 보물상자 x의 열쇠모양입니다. x의 열쇠모양이 α(또는 β)이고 그래서 지도 [x]x를 성공적으로 탐험하기 위한 열쇠 꾸러미는 {-} 가 되는 것입니다.

하지만 이렇게 쉽게 풀리는 경우만 있는것은 아닙니다.
갈림길 e1|e2 의 열쇠모양을 알려면 e1과 e2의 열쇠모양을 알아야 합니다. e1의 열쇠모양이 (α, β)이고 e2의 열쇠모양이 α일 때, 갈림길 e1|e2의 열쇠모양은 β입니다.
구하고자 하는 e1|e2의 열쇠모양 β를 알려면 이미 e1과 e2의 열쇠모양을 알고있어야 합니다. 거꾸로 e1의 열쇠모양을 알고싶으면 e1|e2의 열쇠모양을 알고있어야 하고요. 여러분의 숙제는 이 수수께끼를 풀어내는 것입니다.

어떻게 풀어야 할지 고민해보세요. 꼭 정답이 아니어도 괜찮습니다.