https://adventofcode.com/2022/day/12
휴대용 장치를 사용하여 엘프들과 연락을 시도하지만, 당신이 따라 올라가고 있는 강물이 너무 낮은 위치에 있어 제대로 된 신호를 받을 수 없습니다.
장치에 주변 영역의 높이 지도(퍼즐 입력)를 요청합니다. 높이 지도는 지역을 격자로 나누어 보여줍니다. 격자의 각 사각형의 고도는 하나의 소문자로 표시됩니다. 여기서 a는 가장 낮은 고도, b는 다음으로 낮은 고도 등으로 표시되며, 가장 높은 고도는 z입니다.
높이 지도에는 현재 위치(S)와 신호를 수신하기 가장 좋은 위치(E)에 대한 표시도 포함됩니다. 현재 위치(S)는 고도가 a이고, 신호를 수신하기 가장 좋은 위치(E)는 고도가 z입니다.
당신은 E에 도달하고 싶지만, 에너지를 절약하기 위해 가능한 한 적은 단계로 그곳에 도달해야 합니다. 각 단계마다 당신은 위, 아래, 왼쪽 또는 오른쪽으로 한칸씩 이동할 수 있습니다. 등반 장비를 꺼낼 필요가 없도록, 목적지의 고도는 현재 위치의 고도보다 최대 하나 더 높을 수 있습니다. 즉, 현재 고도가 m인 경우 고도 n으로는 이동할 수 있지만 고도 o로는 이동할 수 없습니다. (이는 또한 목적지의 고도가 현재 위치의 고도보다 훨씬 낮을 수도 있음을 의미합니다.)
아래 예시를 함께 봅시다.
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
위 예시에서는, 왼쪽 상단 모서리에서 시작합니다. 목표는 중간에 가깝습니다. 당신은 아래로 이동하거나 오른쪽으로 이동하는 것으로 시작할 수 있지만, 결국 당신은 하단의 e 쪽으로 이동해야 합니다. 당신은 목표까지 나선형으로 이동하게 될 것입니다.
v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^
위 다이어그램에서 기호는 해당 위치에서 위(^), 아래(v), 왼쪽(<) 또는 오른쪽(>) 중 어디로 이동하는지를 나타냅니다. 신호를 수신하기 가장 좋은 위치는 여전히 E로 표시되며, .은 방문하지 않은 위치를 표시합니다.
이 경로는 31 단계로 목적지에 도착하며, 이는 가능한 가장 적은 단계입니다.
현재 위치에서 신호를 수신하기 가장 좋은 위치로 이동하는 데 필요한 최소 단계는 몇 입니까?
언덕을 올라가니, 엘프들이 이곳을 하이킹 코스로 만들고 싶어할 정도로 아름다웠습니다. 그러나 시작 지점은 그다지 경치가 좋지 않습니다. 당신은 더 나은 시작 지점을 찾을 수 있을 것입니다.
등산을 하는동안 운동량을 늘리기 위해, 경로는 가장 낮은 고도인 a에서 시작해야 합니다. 목표는 여전히 E로 표시된 지역입니다. 그러나 경로는 여전히 직선이어야 하며, 목표에 도달하기 위해 가장 적은 단계를 거쳐야 합니다. 따라서 고도가 a인 지점에서 E로 표시된 지점까지의 최단 경로를 찾아야 합니다.
위의 예를 다시 한번 봅시다.
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
이제 시작 지점으로 여섯 군데를 선택할 수 있습니다. (a로 표시된 5개와, 고도가 a로 간주되는 S로 표시된 지점) 만약 왼쪽 하단 지점에서 시작하면, 가장 빨리 목표에 도달할 수 있습니다.
...v<<<<
...vv<<^
...v>E^^
.>v>>>^^
>^>>>>>^
이 경로는 29 단계로 목적지에 도착하며, 이는 가능한 가장 적은 단계입니다.
고도가 a인 아무 지점에서 시작하여 신호를 수신하기 가장 좋은 위치로 이동하는 데 필요한 최소 단계는 몇 입니까?