최단 거리 길찾기 경우의 수 [확률과 통계]

■ 다음 그림에서 A에서 B까지 최단 거리로 가는 경우의 수를 구하시오.

     (단, 파란색 색칠해진 부분은 호수로 길이 없어 갈 수 없다.)

위와 비슷한 문제가 1990년 학력고사 수학(문과) 시험에 주관식으로 나왔던 거로 기억합니다. 이 문제는 수학 "확률과 통계" 부분에서 "순열"을 이용해서 해결하는 것이 일반적인 풀이법이었습니다. 고등학교 3학년 때, 수학 선생님께서는 이러한 문제는 순열의 정의와 팩토리얼의 개념을 이용해서 풀 수 있지만, 이 문제는 초등학생도 풀 수 있는 문제라며 알려 주셨습니다. 그래서 아마도 그 당시 저와 대부분 친구들은 학력고사에서 초등학교 수준의 덧셈을 이용해서 풀었던 것으로 기억하는데요.

덧셈을 이용한 문제 해결 방법은 이제 많이 보편화 되어서 유튜브나 블로그 등에서 언급되고 있습니다. 또한 현재 고등학생들이 배우는 어떤 수학 교과서에는 이러한 풀이법도 소개하는 것을 보고 저는 격세지감을 느꼈습니다. 

제가 학교 다닐 때는 고등학교 교과서에서 볼 수 없었는데 말이죠.

그럼 덧셈을 이용해서 문제를 풀어 보겠습니다.

아래 그림에서 A에서 B까지 가는 방법은 몇 가지가 있을까요?

어렵지 않게 오른쪽에서 위로 올라가는 방법이 한 가지이고, 위에서 오른쪽으로 가는 방법이 한 가지 있으므로 두 가지임을 알 수 있을 것입니다.

그럼 아래 그림에서  A에서 B까지 가는 방법을 몇 가지가 있을까요?

아래 그림을 참고해 보세요.

위 그램에서 A -> C는 한 가지, A-> E는 한 가지이므로 A-> F까지는 1+1 = 2가지가 됩니다. 또한 A -> D는 한 가지가 됩니다. 왜냐하면 A에서 D까지는  A-> E -> F -> C-> D처럼 가는 방식도 있지만, 최단 거리라고 했으므로 A에서 D까지는 한 가지밖에 없습니다. 따라서 A에서 B까지 가는 방법은 A->F 두 가지에 A-> D 한 가지를 더하면 총 3가지 됩니다.

이제 주어진 문제를 이런 방식으로 계속해서 풀어 보겠습니다.

위 그림에서 빨간색 숫자는 위에서 설명한 방법처럼 각각의 경우의 수를 대각선으로 숫자를 차례로 더한 것입니다. 위의 그림에서 36 숫자 바로 오른쪽에 점까지 얼마인지를 생각하기 위해서 잠시 멈춥니다. 36 숫자 바로 오른쪽까지 가는 방법도 36가지입니다. 왜냐하면 위로 올라갔다가 내려오면 최단 거리가 안 되기 때문이죠. 이제 다시 출발합니다.

이제 아래 방식처럼 최단 거리를 구하면 끝입니다.

생각보다 방법의 수가 많이 나오네요. A에서 B까지 최단 거리 경우의 수는 891가지가 되겠습니다. 혹시 제가 덧셈을 잘 못했으면 댓글로 알려 주세요.

[추가로 풀어보기]

2020년 5월 모의고사 관련 문제

EBS 통계에 따르면 수험생 약 90%가 풀지 못했다는 위 문제도 위와 같은 방식으로 풀어보세요.