어떤 문제인가
격자 모양 도로망에서 A지점에서 P지점을 거쳐 B지점까지 가는 최단경로의 수를 세는 문제예요. 원본 그림의 도로망은 가로 4칸 × 세로 2칸의 완전한 직사각형 격자입니다(세로선 5개, 가로선 3개, 끊긴 길 없음). A를 원점 $(0,0)$으로 두면 B는 우상단 $(4,2)$이고, P는 가운데 가로선과 왼쪽에서 4번째 세로선의 교점인 $(3,1)$이에요. 최단경로이므로 오른쪽·위쪽 이동만 가능하고, 경로 수는 곱의 법칙으로
$$N = N(A\to P) \times N(P\to B)$$
와 같이 두 구간으로 나누어 세요. 각 구간의 경로 수는 이항계수 $\binom{m+n}{m}$으로 셉니다.
단계별 풀이
- **A$(0,0)$ → P$(3,1)$ 구간의 경로 수를 세요.** 오른쪽 3번, 위쪽 1번 이동하므로
$$\binom{3+1}{1} = \binom{4}{1} = 4$$
- **P$(3,1)$ → B$(4,2)$ 구간의 경로 수를 세요.** 오른쪽 1번, 위쪽 1번 이동하므로
$$\binom{1+1}{1} = \binom{2}{1} = 2$$
- 곱의 법칙으로 두 구간을 합쳐요.
$$4 \times 2 = 8$$
검산
각 교점에 "왼쪽 교점의 경로 수 + 아래 교점의 경로 수"를 적어 나가며 그림 위에서 직접 세어 보면 확인할 수 있어요.
- A→P 구간: 아래 행 $1,1,1,1$ / 위 행(중간선) $1,2,3,4$가 되어 P에서 $4$로 확인돼요.
- P→B 구간: $1\times1$ 격자이므로 $2$로 확인돼요.
- 따라서 총 경로 수는 $4\times2=8$입니다.
참고로 그림을 가로 5칸(P$=(4,1)$, B$=(5,2)$)으로 잘못 보고 계산하면 $\binom{5}{1}\times\binom{2}{1}=10$이 되어 ⑤를 고르게 되니 주의해야 해요. 실제 그림은 가로 4칸입니다.
답
$8$ — ③
확인해보기
P를 반드시 지나는 최단경로를 셀 때, 두 구간의 경로 수를 더하지 않고 곱하는 이유를 곱의 법칙으로 설명해 볼까요?