https://adventofcode.com/2019/day/10
당신은 소행성대로 날아가, 세레스에 있는 감시 스테이션에 도착했습니다. 이곳의 엘프들은 현재 소행성 모두를 추적할 수 없어 자신들이 안전한지 알 수 없는 비상상황에 빠져있습니다.
그래서 엘프들은 근처 우주에 새로운 감시 스테이션을 설치하려 하고 있습니다. 그들은 당신에게 그 지역의 모든 소행성들의 위치가 표시된 지도(퍼즐의 입력)를 건네주었습니다.
그 지도는 해당 지역이 비어 있는지(.), 소행성이 있는지(#)를 보여주고 있었습니다. 각 소행성들은 실제로는 지도에 표시된 것보다 훨씬 작고, 또한 지도에 표시된 좌표의 정 가운데에 위치하고 있습니다. 각 소행성의 위치는 X,Y 좌표로 나타낼 수 있는데, 이는 X가 왼쪽 끝에서의 거리, Y가 위쪽 끝에서의 거리를 의미합니다. (즉 지도의 맨 왼쪽 위는 0,0, 그 바로 오른쪽은 1,0이 됩니다.)
당신은 어떤 소행성이 새 감시 스테이션을 짓기에 최적의 장소인지를 알아내어야 합니다. 감시 스테이션은 스테이션에서 바로 시야에 들어오는 소행성들만 관측할 수 있습니다. 다시 말해, 스테이션과 스테이션에서 보이는 소행성 사이에 다른 소행성은 존재할 수 없습니다. 이 시야는 축과 나란하거나, 대각선일 수도 있지만, 그렇지 않고 어떤 각도여도 상관없습니다. 관측할 수 있는 다른 소행성의 개수가 가장 많은 소행성이 감시 스테이션을 짓기에 최적의 장소입니다.
예를 들어, 다음과 같은 지도가 있다고 생각해 봅시다.
.#..#
.....
#####
....#
...##
감시 스테이션을 짓기에 최적의 위치는 좌표 3,4(왼쪽에서 네 번째, 위에서 5번째 칸)에 있는 소행성입니다. 이곳에서 관측할 수 있는 소행성의 갯수는 총 8개로, 다른 어떤 소행성에서보다 많기 때문입니다. (이 곳에서 관측할 수 없는 유일한 소행성은 1,0 하나뿐이며, 이는 2,2에 있는 소행성에 의해 가려지기 때문입니다.) 다른 모든 소행성들에서 관측 가능한 소행성의 개수는 7개 이하입니다. 각 소행성에 감시 스테이션을 세웠을 때 감시할 수 있는 소행성의 갯수를 지도에 표시하면, 다음과 같습니다.
.7..7
.....
67775
....7
...87
여기 소행성(#) 하나를 기준으로 다른 소행성들의 관측 여부를 나타낸 지도가 있습니다. 관측 가능한 소행성들은 대문자로, 다른 소행성에 가려져 관측이 불가능한 소행성들은 소문자로 나타냈습니다.
#.........
...A......
...B..a...
.EDCG....a
..F.c.b...
.....c....
..efd.c.gb
.......c..
....f...c.
...e..d..c
좀 더 큰 예시를 몇 개 더 들어 봅시다.
- 최적의 좌표는
5,8로, 총33개의 소행성을 관측할 수 있습니다.
......#.#.
#..#.#....
..#######.
.#.#.###..
.#..#.....
..#....#.#
#..#....#.
.##.#..###
##...#..#.
.#....####
- 최적의 좌표는
1,2로, 총35개의 소행성을 관측할 수 있습니다.
#.#...#.#.
.###....#.
.#....#...
##.#.#.#.#
....#.#.#.
.##..###.#
..#...##..
..##....##
......#...
.####.###.
- 최적의 좌표는
6,3으로, 총41개의 소행성을 관측할 수 있습니다.
.#..#..###
####.###.#
....###.#.
..###.##.#
##.##.#.#.
....###..#
..#.#..#.#
#..#.#.###
.##...##.#
.....#.#..
- 최적의 좌표는
11,13으로, 총210개의 소행성을 관측할 수 있습니다.
.#..##.###...#######
##.############..##.
.#.######.########.#
.###.#######.####.#.
#####.##.#.##.###.##
..#####..#.#########
####################
#.####....###.#.#.##
##.#################
#####.##.###..####..
..######..##.#######
####.##.####...##..#
.#####..#.######.###
##...#.##########...
#.##########.#######
.####.#.###.###.#.##
....##.##.###..#####
.#.#.###########.###
#.#.#.#####.####.###
###.##.####.##.#..##
새로운 감시 스테이션을 지을 최적의 장소를 찾으세요. 그 곳에서는 총 몇 개의 소행성을 관측할 수 있나요?
당신이 감시 스테이션을 지을 좌표를 알려주자, 요정들은 재빨리 임시 감시 스테이션을 그 곳에 세웠습니다. 그리고는 더 안 좋은 현실에 맞닥뜨리게 되었습니다. 소행성이 너무나 많았던 겁니다.
이를 해결할 유일한 방법은 거대 레이저를 사용해 소행성을 완전히 날려 버리는 것 뿐이었습니다.
다행히, 새 감시 스테이션은 소행성 감지기에 뿐만 아니라 회전 가능한 완벽한 거대 레이저를 갖추고 있습니다. 레이저는 위쪽을 향해서 발사를 시작하여, 항상 시계 방향으로만 회전하며, 레이저가 닿는 모든 소행성을 증발시켜 버릴 겁니다.
만약 직선상에 여러 개의 소행성이 있다면, 레이저는 그 중 가장 가까운 하나만 날려 버리고 다시 회전합니다. 다른 말로, 한 소행성을 날려버림으로써 다른 행성을 관측할 수 있게 된다면, 새롭게 관측된 소행성은 레이저가 한 바퀴 돌아오기 전까지는 그대로 남아있을 것입니다.
다음 지도를 봅시다. 감시 스테이션(그리고 레이저)는 X로 표시된 위치에 있습니다.
.#....#####...#..
##...##.#####..##
##...#...#.#####.
..#.....X...###..
..#.#.....#....##
처음 날아가는 아홉 개의 소행성은 순서대로 다음과 같습니다.
.#....###24...#..
##...##.13#67..9#
##...#...5.8####.
..#.....X...###..
..#.#.....#....##
몇몇 소행성들이(1, 5, 7 뒤에 있는 것들)이 날아가지 않았음에 주목해 주세요. 이들은 레이저가 한 바퀴 돌아온 뒤에 날아갈 것입니다. 레이저는 계속해서 돌아가며, 이어서 지워지는 9개의 소행성은 다음과 같습니다.
.#....###.....#..
##...##...#.....#
##...#......1234.
..#.....X...5##..
..#.9.....8....76
또 이어서 지워지는 9개의 소행성은 다음과 같습니다.
.8....###.....#..
56...9#...#.....#
34...7...........
..2.....X....##..
..1..............
레이저가 한 바퀴를 전부 돌고(1 ~ 3), 두 번째 바퀴에서 몇 개의 소행성이 더 날아가고(4 ~ 8), 세 번째 바퀴까지 돌며 마지막 소행성(9)를 없애면서 주변 청소가 끝날 것입니다.
......234.....6..
......1...5.....7
.................
........X....89..
.................
위에 있는 큰 예시(감시 스테이션을 11,13에 지은 예시)에서는 다음과 같이 지워집니다.
- 첫 번째로 지워지는 소행성은
11,12에 위치해 있습니다. - 두 번째로 지워지는 소행성은
12,1입니다. - 세 번째로 지워지는 소행성은
12,2입니다. - 10번째로 지워지는 소행성은
12,8입니다. - 20번째로 지워지는 소행성은
16,0입니다. - 50번째로 지워지는 소행성은
16,9입니다. - 100번째로 지워지는 소행성은
10,16입니다. - 199번째로 지워지는 소행성은
9,6입니다. - 200번째로 지워지는 소행성은
8,2입니다. - 201번째로 지워지는 소행성은
10,9입니다. - 299번째이자 마지막으로 지워지는 소행성은
11,1입니다.
요정들은 200번째로 지워지는 소행성이 무엇일지 내기를 하기 시작했습니다. 정답을 시뮬레이션해서 내기에서 이기세요. 그 소행성의 X 좌표에 100을 곱한 갑세 Y 좌표를 더하면 얼마인가요? (예를 들어, 8,2이면 802가 됩니다)