도로망 최단경로

[출제의도] 같은 것이 있는 순열을 활용하여 문제 해결하기

그림과 같이 세 지점 $\mathrm{Q _{1} , Q _{2} , Q _{3}}$을 정하면 $\mathrm{A}$지점에서 출발하여 $\mathrm{P}$지점까지 가기 위해서는 $\mathrm{Q _{1}}$지점 또는 $\mathrm{Q _{2}}$지점 중 한 지점을 지나야 하고 $\mathrm{P}$지점에서 출발하여 $\mathrm{B}$지점까지 가기 위해서는 $\mathrm{Q _{2}}$지점 또는 $\mathrm{Q _{3}}$지점 중 한 지점을 지나야 한다. 그러므로 $\mathrm{A}$지점에서 출발하여 $\mathrm{P}$지점을 지나 $\mathrm{B}$지점으로 갈 때, 한 번 지난 도로는 다시 지나지 않으면서 최단거리로 가는 경우의 각각의 경우의 수는 다음과 같다. (ⅰ) $\mathrm{A \rightarrow Q _{1} \rightarrow P \rightarrow Q _{2} \rightarrow B}$의 순서로 이동하는 경우 $\displaystyle \frac{4 !}{1 ! \times 3 !} \times 1 \times 1 \times 1 \times \frac{4 !}{2 ! \times 2 !} = 24$ (ⅱ) $\mathrm{A \rightarrow Q _{1} \rightarrow P \rightarrow Q _{3} \rightarrow B}$의 순서로 이동하는 경우 $\displaystyle \frac{4 !}{1 ! \times 3 !} \times 1 \times 1 \times \frac{5 !}{2 ! \times 3 !} = 40$ (ⅲ) $\mathrm{A \rightarrow Q _{2} \rightarrow P \rightarrow Q _{3} \rightarrow B}$의 순서로 이동하는 경우 $\displaystyle \frac{3 !}{1 ! \times 2 !} \times 1 \times 1 \times 1 \times \frac{5 !}{2 ! \times 3 !} = 30$ (ⅰ), (ⅱ), (ⅲ)에 의해 구하는 경우의 수는 $24 + 40 + 30 = 94$