[신채환]

과제 4의 4번 문제와 관련하여 질문이 있어 글을 올리게 되었습니다.

4번 문제의 상황은 주어진 지도에 대하여 모든 보물 상자를 열 수 있는 최소의 열쇠 꾸러미를 알아내는 것입니다. 여기서 '최소'의 의미가 갑자기 여러 가지로 해석될 수 있다는 생각이 들었습니다.

함수 getReady가 반환하여야 할 열쇠 꾸러미는 각 보물 상자를 열 수 있는 최소 크기 열쇠들의 집합이어야 할지, 모든 보물 상자를 열 수 있는 열쇠 집합 중 최소인 집합이어야 할지, 아니면 또 다른 조건의 열쇠 집합이어야 할지 궁금합니다.

예를 들어, 지도가 다음과 같이 주어졌다고 합시다.
(편의상 End t는 t, Branch (m1, m2)는 m1 | m2, Guide (s, m)은 [s]m으로 적었으며, 연산 우선 순위는 Guide가 더 높다고 간주하였습니다.)

[a](a | [b]b) | (c | (([d]d | (e | f)) | g))

이 경우 최소가 어떤 의미인가에 따라 정답이 달라지는 것 같습니다.

① 각 보물 상자를 열 수 있는 최소 크기 열쇠들의 집합
{-, (-, -), (-, (-, -)), (-, ((-, -), -)), ((-, -), -)}
a: ((-, -), -)
b: -
c: (-, ((-, -), -))
d: (-, -)
e: (-, (-, -))
f: -
g: -

이 경우 각 보물 상자의 열쇠가 해당 보물 상자를 열 수 있는 최소의 열쇠이지만, 열쇠 꾸러미에는 총 5개의 열쇠가 있습니다.

② 모든 보물 상자를 열 수 있는 열쇠 집합 중 최소인 집합
{-, (-, -), (-, ((-, -), (-, -))), ((-, -), (-, -))}
a: ((-, -), (-, -))
b: -
c: (-, ((-, -), (-, -)))
d: (-, -)
e: ((-, -), (-, -))
f: (-, -)
g: -

이 경우 각 보물 상자의 열쇠가 해당 보물 상자를 열 수 있는 최소의 열쇠임이 보장되지 않으나, 열쇠 꾸러미에는 4개의 열쇠만 들어 있습니다.
(사실 이 답이 최소인지는 확실하지 않으나, 일단 ①의 경우보다 작으므로 두 조건이 다름을 보이기에는 충분하다 생각하였습니다.)

이때 둘 중 어떤 답을 반환하여야 하는지, 아니면 또 다른 조건에 따라 답을 내야 하는지 궁금합니다.

[수정 1]
예시의 각 경우에서 c를 여는 열쇠 수정

[조대호]

직접 테스트하고 싶으신분들을 위해 지도를 OCaml type으로 적으면

[이재호]

안녕하세요,

굉장히 좋은 질문 감사드립니다. 답변이 늦어져서 죄송합니다.

모양이 제한되지 않은 모든 열쇠모양을 단순히 -로 치환하는 것은 최소의 열쇠꾸러미를 만들어내지 않을 수 있습니다.
단순한 경우에는 이렇게 하여 답과 일치할 수는 있지만, 제시해주신 경우에는 그렇지 않습니다.

문제에서 각 열쇠의 크기를 최소화한다는 것이 아니라 "최소의(열쇠들 크기의 합을 기준으로) 열쇠꾸러미"라고 하였으므로, 원칙적으로 "② 모든 보물 상자를 열 수 있는 열쇠 집합 중 최소인 집합"으로 이해하신 바가 정확합니다.

더 간단한 예시로는, {x, y, (x, (-, -)), ((-, -), y)}를 생각해볼 수 있습니다.
x와 y를 -로 단순히 바꾼다면 {-, (-, (-, -)), ((-, -), -)}로 크기가 7이 되겠지만, x와 y가 (-, -)이라면 {(-, -), ((-, -), (-, -))}로 크기가 6인 더 작은 열쇠꾸러미를 만들 수 있습니다.

이를 정확히 구현하는 것도 재밌는 퍼즐이 되겠지만, 일단 여기까지 (치환을 고민하는 단계) 오신 것만으로도 많은 고민을 거쳤을 것으로 생각됩니다.
교수님께서 수업 시간에 말씀하신 것과 같이 본 과제에서는 "최선을 다하여 푸시면" 목적을 달성한 것으로 보겠습니다.

감사합니다.

조교 드림


TA 이재호
e-mail: jhlee@ropas.snu.ac.kr

[신채환]

답변해 주셔서 감사합니다!