자연계열 3번

점 A에서 점 B로 가는 최단 경로들은 아래의 그림에서 위에 줄지어 있는 8개의 점을 차례로 지나가는 경우와 아래에 줄지어 있는 6개의 점을 차례로 지나가는 두 가지의 경우로 나뉜다.

위의 8개의 점을 차례로 지나가는 최단경로의 수는 1×2×2×2×2×2×2×2×1 = 128개이다.

아래의 6개의 점을 차례로 지나는 최단경로의 수는 32개이다.

따라서 총 최단경로의 수는 160개이다.

점 A에서 점 C로 가기 위해서는 아래의 5개점 중 하나를 지나야 한다. 이 점들을 아래로부터 차례로 a, b, c, d, e 라고 하자.

A에서 a까지의 최단경로의 길이는 17, a에서 C까지의 길이는 17이므로, a를 경유하는 최단경로의 길이는 34이다.

A에서 b까지의 최단경로의 길이는 14, b에서 C까지의 최단경로의 길이는 14이므로, b를 경유 하는 최단경로의 길이는 28이다.

A에서 c까지의 최단경로의 길이는 14, c에서 C까지의 최단경로의 길이는 10이므로, c를 경유하는 최단경로의 길이는 24이다.

A에서 d까지의 최단경로의 길이는 16, d에서 C까지의 최단경로의 길이는 8이므로, d를 경유하는 최단경로의 길이는 24이다.

A에서 e까지의 최단경로의 길이는 18, e에서 C까지의 최단경로의 길이는 8이므로, e를 경유하는 최단 경로의 길이는 26이다.

따라서, A에서 C까지의 최단경로는 c 또는 d를 경유하여야 한다.

A에서 c로가는 최단경로의 수가 16개이며, c에서 C로 가는 최단경로의 수가 8개이므로, c를 경유하는 최단경로의 수는 128개이다.

A에서 d로가는 최단경로의 수가 32개, d에서 C로 가는 최단경로의 수가 8개이므로, d를 경유하는 최단경로의 수는 256개이다.

따라서, A에서 C로 가는 최단경로의 수는 384개이다.