경우의 수 - 경로의 수 Pt. 1

차례
1. 경로의 수 문제
2. 최단경로의 개수(111 방법)
3. 최단경로의 개수(동자 순열의 활용)
4. 최단경로의 개수(조합의 활용)
5. 최단경로가 아닌 경로의 개수
6. 경로의 수의 활용

앞으로 여러 문제가 나올 것입니다. 그 문제마다 해설을 바로 보기보단 직접 생각해 보시기 바랍니다 :)

---

경로의 수 문제

수학 교과에서 다음과 같은 문제를 본 적이 있을 것이다.

문제: A에서 B까지 지도의 격자점만을 지나 이동하는 최단경로의 개수를 구하시오.

지도

앞으로 경로의 수에서는 기본적으로 이렇게 생긴 문제를 가지고 조금씩 변형해가며 문제를 풀 것이다. 우선은 이렇게 생긴 문제의 해법에 대해 알아보자.

최단경로의 개수: 111 방법

이 방법은 가장 쉽고 간단한 방법이다.

일반적으로 생각했을 때, 최단경로로 이동하려면 모든 움직임은 B를 향해 움직여야 하며, 낭비되는 움직임이 없어야 한다. 다시 말해, 우리는 오른쪽, 아래로만 움직여야 한다.

Fig2-1

그렇다면 전체 문제를 나누어 생각해보자. Fig2-1의 빨간 점까지 이르는 최단경로는 어떻게 구할 수 있을까?

앞서 생각해본 조건에 따라 빨간 점의 바로 이전에 있을 수 있는 점은 분홍색, 파란색 점이다. 그렇다면 합의 법칙에 의해 빨간 점까지 갈 수 있는 경로의 수는 (분홍색까지의 최단경로)+(파란색까지의 최단경로)로 생각할 수 있다.

 

이를 조금 더 일반화하면 다음과 같이 생각할 수 있다: 임의의 한 점까지 이르는 최단경로의 개수는 이전 2개 점에서의 최단경로의 개수의 합이다.

Fig2-2

이제 이 방법으로 문제를 풀어보자. 우선은 최단경로의 개수가 자명히 1인 지점(분홍색)을 모두 써준다.

 

그리고 색 있는 화살표와 같은 방향으로 더해서 두 화살표가 가리키는 지점의 최단경로의 수를 새롭게 구한다. 이 과정을 반복하면 격자점에 Fig2-2와 같이 최단경로의 개수를 이어서 써줄 수 있으며 결국 B까지 최단경로는 70개이다.

 

이 방법을 정확히 무슨 방법이라고 하는지는 모르겠다만 나는 111방법이라고 한다. 최단경로의 개수가 1개인 점에서 반복하여 계산을 시작하기 때문이다.

이 방법은 직관적이며 계산도 어렵지 않다. 따라서 크기가 작은 지도에서 빠르게 최단경로를 구할 때 유용하다. 이를테면 2x3크기의 지도에서는 후술 할 다른 방법보다 111방법이 훨씬 편하고, 빠르며 유용하다. 하지만, 서술형과 같이 풀이과정을 써야 할 땐 가급적 지양해야 하는 방법이다. 이 방법은 전체 경로의 수를 일일이 구하는, 일명 노가다와 다를 바 없기 때문이다.

---

최단경로의 개수: 동자 순열의 활용

111방법은 분명한 한계가 있다. 지도가 너무 크거나 해서 덧셈을 많이 해야 하면 시간은 물론 실수가 있을 확률도 무시 못하게 커진다. 따라서 다른 방법을 생각해야 한다.

Fig3-1

이번에는 5x4 크기의 지도를 생각해보자. A에서 B까지 최단경로로 간다고 치면 어느 경로를 선택하던 그 경로는 오른쪽으로 5번, 아래로 4번을 이동하여 총 9번을 이동해야 한다. 이보다 더 짧은 경로는 없다.

 

그렇다면 최단경로의 개수를 총 9번을 이동할 건데 그중 5번을 오른쪽으로 가는 경우, 또는 9번을 이동하는데 그중 4번을 아래로 이동하는 경우로 생각할 수 있다.

 

동자 순열을 복습해보자. $n$개의 공중에서 빨간색 공이 $a$개, 초록 색공이 $b$개다. 같은 색의 공은 서로 구별되지 않을 경우 $n$개의 공을 나열하는 경우의 수는 $\frac {n!}{a! b!}$이였다.

이를 똑같이 적용하여 9번 움직이는데 5번은 오른쪽을, 4번은 아래쪽을 선택하는 경우의 수로 생각할 수 있다. 따라서 $\frac{9!}{5!4!}$$=\frac{6 \times 7 \times 8 \times 9}{4!}$$=126$가지이다.

 

앞서 탐구했던 내용을 더욱 일반화하여, $n \times m$크기의 직사각형 지도에서 한 꼭짓점에서 마주 보는 다른 꼭짓점까지 격자점만을 지나 이르는 최단경로의 개수는 $\frac{(n+m)!}{n!m!}$으로 구할 수 있겠다. $n+m$번 움직일 건데 $n$번 왼쪽으로, $m$번 아래로 이동하도록 이동을 구성하는 경우의 수이다.

---

최단경로의 개수: 조합의 활용

앞서 알아본 것처럼 동자 순열을 이용할 수도 있지만 우리는 조합을 이용해서도 최단경로의 수를 구할 수 있다.

Fig4-1

다시 이렇게 생긴 5x4크기의 지도를 생각해보자. 우리는 9번을 움직일 것이며 왼쪽으로 5번, 아래로 4번 움직여야 한다. 즉, 9번 중에 5번 오른쪽으로 움직이거나, 4번 아래로 움직이는 경우의 수를 구하면 된다.

즉, 9번 움직이는 방법을 구할 것인데 오른쪽으로 5번가는 경우의 수를 구하고 나머지 4번은 반드시 내려간다고 생각하거나, 9번 중 4번을 내려가는 경우의 수를 구하고 나머지 5번을 모두 오른쪽으로 간다고 생각할 수 있다.

 

각각의 경우를 수식으로 표현하면 9번의 움직임 중 오른쪽으로 가는 이동을 5개 뽑는 경우의 수는 ${}_9\mathrm C_5$이며, 9번의 움직임 중 아래로 가는 이동을 4개 뽑는 경우의 수는 ${}_9\mathrm C_4$이다. 당연하게도 이 두 식의 값은 같다. 식의 의미가 같기 때문이다.

즉, 최단경로의 개수가 ${}_9\mathrm C_4$$=\frac{9!}{4!5!}$$=126$가지임을 알 수 있다.

 

이번에도 일반화하여, $n \times m$크기의 직사각형 지도에서 한 꼭짓점에서 마주 보는 다른 꼭짓점까지 격자점만을 지나 이르는 최단경로의 개수는 ${}_{(n+m)}\mathrm C_n$$={}_{(n+m)}\mathrm C_m$가지이다. 두 방법 모두 같은 결과가 나오고 의미도 같으므로 적당히 계산하기 편한 걸 골라서 쓰면 되겠다.

 

 

---

최단경로가 아닌 경로의 개수

앞서서는 최단경로의 개수만을 구하였다. 하지만 언제나 최단경로만을 움직일 수는 없지 않은가. 이번에는 최단경로가 아닌 경로의 개수를 찾는 방법에 대해 정리해보겠다.

Fig5-1

또 이 지도이다. 이 지도에서 최단경로는 9번 이동하는 경우인데 9번 대신 11번 이동하여 B에 도달하는 경우의 수를 생각해보자. 지도의 격자점만을 지날 수 있으며 지도를 벗어날 수는 없다.

 

이 문제는 앞서 알아본 방법을 그대로 적용하기 어려움이 있을 듯하다. 우선 문제에서 이동하는 데 있어 조건들을 몇 개 찾아보면 최단경로가 아니기 때문에 왼쪽으로 움직일 수도 있고 위로 움직일 수도 있다. 다만, 지도 밖으로 이동할 수는 없다.

 

일단 경우를 두가지로 나누어보자:

경우 1: 최단경로에서 왼쪽으로 1번, 오른쪽으로 1번 움직이는 경우

왼쪽으로 1회, 오른쪽으로 1회 움직이면 결국 제자리이니 이동 중에 왼쪽으로 1번, 오른쪽으로 1번 움직이는 경우를 생각할 수 있다. 하지만, 주의해야 할 것이 왼쪽으로 가면 지도를 벗어나는 경우에는 왼쪽으로 움직일 수 없다. 또한 마지막 수평이동이 왼쪽이면 지도에 도달할 수 없다. 안되는 경우의 수를 전체에서 빼줘야 한다.

전체 경우의 수는 → 6개, ← 1개, ↓4개로 동자 순열에 따라 $\frac{11!}{6!1!4!}$개이다. 그리고 그중에서 ←가 처음, 혹은 마지막 수평이동인 경우를 각각 빼주어야 하니 $-2(\frac{11!}{7!4!})$(가장 먼저있는, 혹은 마지막인 →를 ←로 바꾸어 생각할 수 있다.) 따라서 전체적인 식은 $\frac{11!}{6!1!4!}-2(\frac{11!}{7!4!})$으로 총 1650가지 경우이다.

 

경우 2: 최단경로에서 위로 1번, 아래로 1번 움직이는 경우

경우1과 같게 생각한다. 전체경우는 → 5번, ↓ 5번, ↑ 1번이다. 따라서 $\frac{11!}{5!5!1!}-2(\frac{11!}{5!6!})$으로 총 1848가지이다.

 

답:

경우 1과 경우 2는 개별적으로 일어나는 사건이므로 합의 법칙에 따라 $1650+1848=3498$가지, 정답은 $3948$가지이다.

---

경로의 수의 활용

(당연하지만) 앞으로 몇x몇 크기의 지도에서 어느 지점에서 지점까지 최단경로를 구하라는 문제는 나오지 않는다. 너무 쉽기 때문이다. 그 대신 경로의 수의 아이디어를 이용해서 쉽게 풀 수 있는 문제들이 나올 것이다. 경우의 수를 접목하여 다음 문제들을 풀어보자.

 

참고: 답이 굉장히 크고 계산하기 어렵게 나올 수 있다. 이때는 팩토리얼을 실제로 계산하기보단 식의 형태로 답을 내어도 좋다.

 

1. 조금만 빨리빨리

미호는 약속에 늦어서 약속장소로 뛰어오고 있다.

미호가 A에 다다르자 미호는 B에 있는 친구가 7초 이내로 뛰어오라는 말을 하는 것을 들었다.

그래서 미호는 7초 이내로 뛰어가려고 한다. 하지만 미호는 체력적으로 힘들기 때문에 인접한 격자점사이를 1초동안 움직일 예정이다.

이때, 미호가 친구에서 뛰어갈 수 있는 경로의 개수를 구하여라.

단, 미호는 격자점만을 검은 선을 따라 움직일 수 있으며 지도를 벗어날 수 없다.

 

 

2. 투표의 진행

후보자 2명 갑과 을이 유권자 12명에 대해 투표를 진행하고자 한다.

두 후보자가 1:2로 표를 나누어 가져 을이 승리하였을때, 투표가 진행될 수 있는 경우의 수를 구하여라.

참고: 투표가 진행될 경우의 수라 함은, 투표의 결과가 같더라도 개표가 다르게 이루어지면 다른 경우로 보는 것이다. 예를 들어 AAB, BAA와 같이 A, B가 표를 얻은 경우 결과는 같지만 투표가 진행된 경우는 다르다.

 

3. 세 곳으로 이동

4x4크기의 지도가 있다. 가장 왼쪽 아래에 있는 점을 A(0,0), 가장 오른쪽 위에 있는 점을 B(4,4)라고 할 것이다.

A에서 B까지 정수점만을 지날 것이며 x좌표를 1 증가시키는 이동{(0,0)→(1,0)}, y방향을 1 증가시키는 이동{(0,0)→(0,1)}, x, y모두 1 증가하는 이동{(0,0)→(1,1)}까지 3가지 이동을 이용하여 A에서 B까지 이동하려고 한다.

이동하는 경우의 수는 몇 가지인가?

 

1. 7번 이동하면 되는 것이다. 경우를 나누어서 기존 최단경로에 왼쪽 오른쪽을 추가로 이동하는 경우, 위아래를 추가로 이동하는 경우를 나누어 각각 구하고 더하면 될 것이다.
Case 1. → 4번, ← 1번, ↓ 2번을 이동하는 경우: 동자 순열을 이용하여 $\frac{7!}{4!2!1!}$이다.
Case 2. → 3번, ↑ 1번, ↓ 3번을 이동하는 경우: 동자 순열을 이용하여 $\frac{7!}{3!3!1!}$이다.
두 경우는 각각 일어나는 사건이므로 합의 법칙에 따라 $\frac{7!}{4!2!1!}+\frac{7!}{3!3!1!}$$=105+140$$=245$가지이다.
이번 문제에서는 위의 최단경로가 아닌 경로의 수에서 다룬 것처럼 왼쪽, 혹은 위로 움직이는 경우가 처음인 경우, 마지막인 경우를 빼주지 않았다. 그 이유는 처음으로, 혹은 마지막으로 그런 이동을 해도 지도를 벗어나거나 도착할 수 없게 되는 그런 일은 없기 때문이다.

2. 12명이 투표하여 1:2로 득표하면 A는 4표, B는 8표를 얻는 것이다. 이젠 4x8 크기의 지도를 생각해보자. 이 지도의 A지점(말 안 해도 어딘지 알 것이다.)에서 B지점(여기도 어딘지 알 것이다.)으로 이동하는데 A가 득표하면 왼쪽으로, B가 득표하면 위로 이동하자. 그럼 개표가 진행되는 경우의 수는 A에서 B까지 12번 이동하여(최단경로이다) 도착하는 경우의 수이다. 따라서 경우의 수는 $\frac{12!}{8!4!}$$=495$가지이다.

3. 경우를 나누어 생각해 볼 것인데 아무래도 대각선으로 1번, 2번... 이동하는 경우가 적을 것이니 대각선으로 1~4번 움직이는 경우로 나누고 합의 법칙을 이용하자.
1. 대각선으로 1회 움직이는 경우: ↗ 1번, → 3번, ↑ 3번으로 동자 순열에 따라 $\frac{7!}{1!3!3!}$$=140$
2. 대각선으로 2회 움직이는 경우: ↗ 2번, → 2번, ↑ 2번으로 동자 순열에 따라 $\frac{6!}{2!2!2!}$$=90$
3. 대각선으로 3회 움직이는 경우: ↗ 3번, → 1번, ↑ 1번으로 동자 순열에 따라 $\frac{5!}{3!1!1!}$$=20$
4. 대각선으로 4회 움직이는 경우: ↗ 4번, → 0번, ↑ 0번으로 동자 순열에 따라 $\frac{4!}{4!0!0!}$$=1$
합의 법칙에 따라 $140+90+20+1$$=251$가지이다.
참고: $0!=1$이다.