https://adventofcode.com/2019/day/3
스윙바이는 성공적이었고, 당신은 이제 금성에 있는 연료 보급소를 향해 가고 있습니다. 그러나 지구에서 너무 급하게 출발한 바람에 연료 관리 시스템의 설치가 덜 되었고, 이제 이 작업을 마무리해야 합니다.
앞쪽 패널을 열자 뒤범벅된 전선들이 눈에 들어옵니다. 특히, 두 개의 전선이 중앙 포트에 연결되어 바깥으로 뻗어나가는 것이 눈에 띕니다. 당신은 중앙 포트로부터 출발한 두 전선을 따라가며, 이를 각 전선마다 다른 줄에 기록하였습니다.
두 전선은 꼬이거나 휘어지면서 이따금 교차하기도 합니다. 회로를 고치기 위해서는 중앙포트에서 가장 가까이 있는 교차점을 찾아야 합니다. 전선은 격자 위에 위치하고 있기 때문에, 거리를 재는 방법으로는 맨하탄 거리(Manhattan Distance)를 사용하기로 합니다. 그리고 중앙 포트에서도 두 전선이 교차하긴 하지만, 이 점은 교차하는 점으로 생각하지 않습니다.
예를 들어, 첫 번째 전선의 경로가 R8,U5,L5,D3인 경우, 중앙 포트(o)에서 시작해서 차례로 오른쪽으로 8칸, 위로 5칸, 왼쪽으로 5칸, 아래로 3칸에 걸쳐 전선이 위치합니다.
...........
...........
...........
....+----+.
....|....|.
....|....|.
....|....|.
.........|.
.o-------+.
...........
두 번째 전선의 경로가 U7,R6,D4,L4인 경우, 중앙 포트(o)에서 시작하여 차례로 위로 7칸, 오른쪽으로 6칸, 아래로 4칸, 왼쪽으로 4칸에 걸쳐 전선이 위치합니다.
...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........
이 두 전선은 X로 표시된 두 곳에서 교차하는데, 이중 왼쪽 아래의 교차점이 중앙 포트에 가장 가깝습니다. 그리고 이 때의 거리는 3 + 3 = 6 입니다.
여기 몇 가지 예시가 더 있습니다.
R75,D30,R83,U83,L12,D49,R71,U7,L72U62,R66,U55,R34,D71,R55,D58,R83 = distance 159R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = distance 135
중앙 포트와 가장 가까운 교차점의 맨하탄 거리는 얼마입니까?
이 회로는 시간에 매우 민감합니다. 그래서 당신은 신호의 지연을 최소화해야 합니다.
그러기 위해서, 우선 각 교차점에 다다르기 위한 각 전선의 길이를 계산합니다. 그리고 모든 교차점들 중 필요한 전선들의 길이의 합이 가장 작은 교차점을 선택해야 합니다. 만약 하나의 전선이 격자 위의 특정 지점을 두 번 이상 지난다면, 그 지점에 처음 다다르는 순간의 길이로 계산하면 됩니다.
필요한 전선의 길이는 교차점을 포함하여 해당 위치까지 지나온 격자의 개수입니다. 위의 예시를 다시 한 번 사용해봅시다.
...........
.+-----+...
.|.....|...
.|..+--X-+.
.|..|..|.|.
.|.-X--+.|.
.|..|....|.
.|.......|.
.o-------+.
...........
중앙 포트에서 가장 가까운 교차점까지 첫 번째 전선은 8+5+5+2 = 20칸이며, 두 번째 전선은 7+6+4+3 = 20칸이 필요하므로, 필요한 전선의 총 길이는 20 + 20 = 40입니다.
오른쪽 교차점은 더 나은 값을 가집니다. 첫 번째 전선은 8+5+2 = 15칸이 필요하고, 두 번째 전선은 7+6+2 = 15칸이 필요하므로, 총 길이는 15 + 15 = 30입니다.
위의 추가 예시들에 대한 최소 길이는 다음과 같습니다.
R75,D30,R83,U83,L12,D49,R71,U7,L72U62,R66,U55,R34,D71,R55,D58,R83 = 610 stepsR98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = 410 steps
두 전선이 교차점에 다다르기 위한 전선 길이의 합의 최소 값은 얼마입니까?