https://adventofcode.com/2022/day/8
원정대는 큰 나무들이 격자 모양으로 심어진 독특한 땅을 발견했습니다. 엘프들은 이전 원정대가 숲을 다시 가꾸기 위해 이 나무를 심었다고 설명합니다. 지금, 그들은 이곳이 트리하우스를 짓기 좋은 위치인지 궁금해 합니다.
먼저 여기에 트리하우스를 숨길 수 있을 만큼 충분히 나무가 덮여있는지 확인해야 합니다. 이를 위해선, 행이나 열을 따라 직접 볼 때 격자 외부에서 볼 수 있는 나무의 수를 세어야 합니다.
엘프들은 이미 쿼드콥터를 사용해서, 각 나무의 높이가 포함된 지도(퍼즐 입력)를 생성했습니다. 예를 들어 지도가 다음과 같다고 가정해봅시다.
30373
25512
65332
33549
35390
각 나무는 높이를 나타내는 단일 숫자로 표시됩니다. 여기서 0는 가장 낮고 9가 가장 높습니다.
나무는 자신과 격자 가장자리 사이의 다른 모든 나무가 자기보다 낮은 경우 관측이 가능해집니다. 오직 같은 행이나 열에 있는 나무만 고려해야 합니다. 즉, 주어진 나무에서 위, 아래, 왼쪽 또는 오른쪽만 보면 됩니다.
격자 가장자리에 심어진 모든 나무는 관측이 가능합니다. 이미 가장자리에 있기 때문에 시야를 가리는 나무가 없습니다. 그러니 위 예시에서 격자 내부에 있는 나무 9그루만 계산해봅시다.
- 상단-좌측의 나무(높이
5)는 왼쪽과 위쪽에서 볼 수 있습니다. (오른쪽과 밑에서는 높이가5보다 높은 다른 나무들이 가로막고 있어 보이지 않습니다) - 상단-중앙의 나무(높이
5)는 위쪽과 오른쪽에서 볼 수 있습니다. - 상단-우측의 나무(높이
1)은 어떤 방향에서도 보이지 않습니다. 이 나무가 보이려면 해당 나무와 가장자리 사이에 높이가0인 나무들만 있어야 합니다. - 중단-좌측의 나무(높이
5)는 오른쪽에서 볼 수 있습니다. - 중심의 나무(높이
3)은 어느 방향에서도 보이지 않습니다. 이 나무가 보이려면 해당 나무와 가장자리 사이에 높이가2이하인 나무들만 있어야 합니다. - 중단-우측의 나무(높이
3)는 오른쪽에서 볼 수 있습니다. - 하단 행에서는, 중간의 나무(높이
5)는 보이지만, 높이가3,4인 나무들은 보이지 않습니다.
가장자리에 심어진 16그루의 나무를 볼 수 있고, 격자 내부에 볼 수 있는 5그루의 나무가 있기 때문에, 위 예시에서는 총 21그루의 나무가 보입니다.
당신의 지도를 보았을 때, 격자 외부에서 몇 그루의 나무를 볼 수 있습니까?
트리하우스를 가릴만큼 충분한 나무가 있는 것에 만족한 엘프들은 트리하우스를 지을 최적의 위치를 알고싶어 합니다. 그들은 가능한 많은 나무를 보고싶어 합니다.
주어진 나무에서 볼 수 있는 나무의 개수를 측정하려면, 해당 나무를 기준으로 위쪽, 아래쪽, 왼쪽과 오른쪽을 살펴봐야 합니다. 기준이 되는 나무와 높이가 같거나 더 큰 나무 혹은 격자의 가장자리에 도달하면, 측정을 멈춥니다. (나무가 가장자리에 있으면, 적어도 한 방향에 대해 볼 수 있는 나무 개수는 0이 됩니다.)
엘프들은 위의 규칙에 의해 발견된 나무보다 더 멀리 있는 나무에 대해 신경쓰지 않습니다. 설령 그 나무의 높이가 발견된 나무보다 크더라도 말입니다. 왜냐하면, 지어질 트리 하우스는 건조한 상태를 유지하기 위해 큰 처마가 있어서, 어차피 트리 하우스보다 더 높은 나무는 볼 수 없기 때문입니다.
위 예시의 두 번째 행 중간에 있는 높이가 5인 나무에서 측정해봅시다.
30373
25512
65332
33549
35390
- 위쪽을 보면 시야가 차단되지 않습니다. 높이가
3인 나무 하나만 볼 수 있습니다. - 왼쪽을 보면 시야가 즉시 차단됩니다. 바로 왼쪽에 있는 높이가
5인 나무 하나만 볼 수 있습니다. - 오른쪽을 보면 시야가 차단되지 않습니다.
2개의 나무를 볼 수 있습니다. - 아래쪽을 보면 결국에는 시야가 차단됩니다. 여기서는
2개의 나무를 볼 수 있습니다. (높이가3인 나무 하나와 시야를 차단하는 높이가5인 나무)
한 나무의 경치 점수는 네 방향 각각에서 볼 수 있는 나무 개수를 함께 곱하여 구합니다. 위 예시의 나무의 경치 점수는 4(1 * 1 * 2 * 2을 곱하여)입니다.
그러나, 더 좋은 나무를 찾을 수 있습니다. 네 번째 행 중간에 있는 높이가 5인 나무에서 측정해봅시다.
30373
25512
65332
33549
35390
- 위쪽을 보면
2개의 나무가 보입니다. (높이가5인 나무에 의해 시야가 차단됩니다). - 왼쪽을 보면 시야가 차단되지 않습니다.
2개의 나무를 볼 수 있습니다. - 아래쪽을 보면 시야가 차단되지 않습니다.
1개의 나무를 볼 수 있습니다. - 오른쪽을 보면
2개의 나무가 보입니다. (높이가9인 나무에 의해 시야가 차단됩니다).
이 나무의 경치 점수는 8(2 * 2 * 1 * 2)입니다. 여기가 트리 하우스를 짓기에 이상적인 장소입니다.
지도의 모든 나무를 고려했을 때, 가장 높은 경치 점수는 얼마입니까?