도로망 최단경로

그림과 같이 $6$개의 점 $\mathrm{C} _{1} , C _{2} , C _{3} , C _{4} , C _{5} , C _{6}$과 $4$개의 정사각형 $R _{1} , R _{2} , R _{3} , R _{4}$가 있다. 최단거리로 $\mathrm{A}$지점에서 출발하여 $\mathrm{B}$지점을 지나 다시 $\mathrm{A}$지점으로 돌아올 때, 조건 (가)를 만족시키려면 $\mathrm{A} \rightarrow C _{2} \rightarrow B \rightarrow C _{2} \rightarrow A$의 순서로 이동해야 한다. 또한, 조건 (나)를 만족시키려면 정사각형 $R _{1} , R _{2} , R _{3} , R _{4}$ 중 네 변을 모두 지나는 정사각형은 없어야 한다. ⅰ) $\mathrm{C} _{2} \rightarrow B \rightarrow C _{2}$의 순서로 이동하는 경우 ($\mathrm{C} _{2}$에서 $\mathrm{B}$로 가는 경우의 수)$\times$($\mathrm{B}$에서 $\mathrm{C} _{2}$로 가는 경우의 수) $= 2 \times 1 = 2$ ⅱ) $\mathrm{A} \rightarrow C _{2} , C _{2} \rightarrow A$의 순서로 이동하는 경우 $\displaystyle \frac{4 !}{2 ! \times 2 !} \times \frac{4 !}{2 ! \times 2 !} = 6 \times 6 = 36$ $( a )$ 정사각형 $R _{1}$의 네 변을 모두 지나는 경우 $\mathrm{A} \rightarrow C _{3} \rightarrow C _{1} \rightarrow C _{2}$, $\mathrm{C} _{2} \rightarrow C _{1} \rightarrow C _{3} \rightarrow A$의 순서로 이동하는 경우의 수이므로 $( 1 \times 2 \times 1 ) \times ( 1 \times 1 \times 1 ) = 2$ $( b )$ 정사각형 $R _{2}$의 네 변을 모두 지나는 경우 $\mathrm{A} \rightarrow C _{4} \rightarrow C _{2}$, $\mathrm{C} _{2} \rightarrow C _{4} \rightarrow A$의 순서로 이동하는 경우의 수이므로 $( 2 \times 2 ) \times ( 1 \times 2 ) = 8$ $( c )$ 정사각형 $R _{3}$의 네 변을 모두 지나는 경우 $\mathrm{A} \rightarrow C _{4} \rightarrow C _{2}$, $\mathrm{C} _{2} \rightarrow C _{4} \rightarrow A$의 순서로 이동하는 경우의 수이므로 $( 2 \times 2 ) \times ( 2 \times 1 ) = 8$ $( d )$ 정사각형 $R _{4}$의 네 변을 모두 지나는 경우 $\mathrm{A} \rightarrow C _{6} \rightarrow C _{5} \rightarrow C _{2}$, $\mathrm{C} _{2} \rightarrow C _{5} \rightarrow C _{6} \rightarrow A$의 순서로 이동하는 경우의 수이므로 $( 1 \times 2 \times 1 ) \times ( 1 \times 1 \times 1 ) = 2$ $( e )$ 두 정사각형 $R _{2} , R _{3}$의 네 변을 모두 지나는 경우 $\mathrm{A} \rightarrow C _{4} \rightarrow C _{2}$, $\mathrm{C} _{2} \rightarrow C _{4} \rightarrow A$의 순서로 이동하는 경우의 수이므로 $( 2 \times 2 ) \times ( 1 \times 1 ) = 4$ $( a )$~$( e )$에 의하여 $\mathrm{A} \rightarrow C _{2} , C _{2} \rightarrow A$의 순서로 이동할 때, 한 변의 길이가 $1$인 정사각형 중 네 변을 모두 지나는 정사각형이 없는 경우의 수는 $36 - \left\{ ( 2 + 8 + 8 + 2 ) - 4 \right\} = 20$ ⅰ), ⅱ)에 의하여 구하는 경우의 수는 $2 \times 20 = 40$