day6

Day 6: 우주 궤도 지도 (Universal Orbit Map)

https://adventofcode.com/2019/day/6

Part 1

당신은 수성에 있는 우주 궤도 지도 보관소에 착륙했습니다. 우주에서의 항해는 주로 궤도 사이의 이동을 포함하므로, 궤도 지도는 당신과 산타 사이의 최적 경로를 찾는데 도움이 될 것입니다. 당신은 주변 궤도들의 지도(퍼즐의 입력)을 다운로드받았습니다.

우주의 질량 중심(Center of Mass, COM)을 제외하고는 우주의 모든 천체는 다른 한 천체의 주변을 공전합니다. 그림으로 나타내면 대략 이런 식입니다.

                  \
                   \
                    |
                    |
AAA--> o            o <--BBB
                    |
                    |
                   /
                  /

이 다이어그램에서는 BBB 천체가 AAA 주의를 도는 궤도에 있습니다. 선으로 표시된, AAA 주변을 도는 BBB의 궤도는 일부만 보여지고 있습니다. 지도 데이터에서는 이 궤도 관계를 AAA)BBB와 같이 표시하며, 이는 BBB가 AAA의 궤도에 있다는 뜻입니다.

지도를 사용해서 항해 계획을 세우기 전, 당신은 이 지도가 다운로드 도중에 손상되지 않았는지 확인해야 합니다. 지도를 검증하기 위해, **궤도 수 체크섬(orbit count checksums)**을 사용할 수 있습니다. 이것은 직접 궤도(direct orbits)와 간접 궤도(indirect orbits)의 총합을 의미합니다.

A가 B의 궤도이고, B가 C 궤도라면, A는 C의 간접 궤도 입니다. 이 연결은 사이에 있는 천체의 수와 무관하게 이어질 수 있습니다. 만약, A가 B의 궤도이고, B가 C의 궤도이고, C가 D의 궤도이면, A는 D의 간접 궤도입니다.

예를 들어, 다음과 같은 지도가 있다고 해봅시다.

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L

이를 그림으로 나타내면, 다음과 같습니다.

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

이 그림에서 두 천체가 선으로 이어져있을 때, 오른쪽에 있는 천체가 왼쪽에 있는 천체의 직접 궤도입니다.

그러면 이제 우리는 궤도의 개수를 세어볼 수 있습니다.

• D는 C의 직접 궤도이고, B와 COM의 간접 궤도입니다. 즉, 총 3개의 궤도를 가집니다.
• L은 K의 직접 궤도이고, J, E, D, C, B, COM의 간접 궤도입니다. 총 7개의 궤도를 가집니다.
• COM은 궤도가 없습니다.

이 예제에서는 직접 궤도와 간접 궤도의 총 개수가 42개 입니다.

당신의 지도 데이터에 있는 천체들의 직접 궤도와 간접 궤도의 총 개수는 얼마인가요?`

Part 2

이제 당신(YOU)과 산타(SAN) 사이에 얼마나 많은 궤도 이동을 해야하는지 계산해야 합니다.

당신은 YOU가 공전하고 있는 천체에서부터 출발하고, 목적지는 SAN이 공전하고 있는 천체입니다. 한 번의 궤도 이동은 어떤 천체로부터 그 천체가 공전하고 있는, 또는 그 천체를 공전하고 있는 다른 천체로 이동할 수 있게 해줍니다.

예를 들어, 다음과 같은 지도가 있다고 해봅시다.

COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN

그림으로 나타내면 다음과 같습니다.

                          YOU
                         /
        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I - SAN

이 예제에서, 당신은 K의 궤도에 있고, SAN은 I의 궤도에 있습니다. K에서 I로 이동하기 위해서는, 최소한 4번의 궤도 이동이 필요합니다.

• K to J
• J to E
• E to D
• D to I

궤도 이동을 마치고 나면, 지도는 다음과 같은 모양이 될 것입니다.

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I - SAN
                 \
                  YOU

YOU가 공전하고 있는 천체로부터 SAN이 공전하고 있는 천체까지 이동하려면 최소한 몇 번의 궤도 이동을 해야 하나요? (YOU와 SAN 사이가 아니라, 각각이 공전하고 있는 천체 사이의 거리임을 주의하세요.)