[문제 풀이] 경우의 수, 도로망

그림과 같은 도로망에서 다음 조건을 만족하면서 A 지점에서 출발해 B 지점에 도착하는 경우의 수를 구하시오.

그림 : 도로망

(가) A 지점에서 P 지점까지는 →, ↑ 방향으로만 이동할 수 있다.
(나) P 지점에서 B 지점까지는 →, ↘, ↓ 방향으로만 이동할 수 있다.

---

이렇게 경우의 수를 다루는 문제에서는 곱셈, 덧셈 법칙을 이용해 어떻게 세는 것이 효율적인지 잘 파악하는 게 중요하겠죠. A에서 P까지의 경로 개수와 P에서 B까지의 경로 개수는 서로 영향을 미치지 않으니 둘을 곱해 전체 경로 개수를 얻을 수 있어요.

각각의 개수를 구하는 과정에서도 어떻게 세는 게 쉬울지 고민해야겠죠. 먼저 일반적인 '최단 거리로 이동'하는 경우의 수를 찾는 문제와는 다르게 P에서 B까지의 경로에서 대각선으로 이동하는 경우는 그 양 끝점을 지나는 다른 경우와 비교해서 한 칸을 덜 움직인다는 걸 알 수 있어요. 움직이는 횟수를 통일하기 위해서는 대각선으로 표현된 길들의 가운데에 점을 찍어 두 칸으로 세는 게 혼동을 줄일 수 있어요.

P에서 B까지의 필요한 이동 횟수를 통일하기 위해 대각선 방향의 길들을 이동하는 데에 2회가 필요하도록 각각의 가운데에 점을 추가했다.

이제 A에서 P까지와 P에서 B까지의 경로 개수를 각각 세어봐야겠죠. 이동 방향이 제한되어 있기에 각 회차에 지날 수 있는 점은 다른 회차에서 지나는 경우는 없어요. 예를 들어 A의 위에 있는 점과 오른쪽에 있는 점은 모두 한 번 이동했을 때만 머물 수 있죠. 이 두 점을 모두 지나는 일은 없으니 각각의 경우는 배반사건으로 '덧셈 법칙'이 성립해요.

이렇게 각 회차에 지날 수 있는 점들을 살펴보면 A에서 P까지의 도로망은 3회차에서 지날 수 있는 점들을 잇는 직선에 대해 대칭이라는 걸 알 수 있어요. 마찬가지로 P에서 B까지의 도로망은 전체 경로에서 9회차에 지날 수 있는 점들을 잇는 직선에 대해 대칭이죠.

3회차에 지날 수 있는 점들을 기준으로 살펴보면, A에서 이 점들까지의 경로와 이 점들에서 P까지의 경로가 대칭성에 의해 방향만 반대이고 같은 도로망을 가지기에 같은 경우의 수를 가진다는 걸 알 수 있어요. P까지의 경로 개수와 P로부터의 경로 개수에 대해 곱셈 법칙이 적용되는 것과 마찬가지로, 위의 두 경우의 수를 곱해서 각 점들을 지나는 경우의 수를 얻을 수 있죠. 또한, 위에서 설명한 1회차에 지날 수 있는 점들에 대한 설명처럼, 3회차에 지나는 점들에 대해서도 덧셈법칙이 적용된다는 걸 알 수 있어요.

3회차에 지날 수 있는 점 L, C, R.

위 그림에서 표시된 세 점 L, C, R이 바로 3회차에 지날 수 있는 점들이죠. A에서 R까지의 경로는 가로로 세 번 이동하는 경우밖에 없어요. L까지의 경로는 L의 바로 아래에 있는 점을 지나야 하고, 이 점에 오는 경로는 1회차에 지날 수 있는 두 점을 지나는 두 경우로 2가지라는 걸 알 수 있죠. C까지의 경로는 총 세 번의 이동 중 세로로 이동하는 회차를 선택하는 방법으로 셀 수 있어요. 즉, 곱셈 법칙에 의해 A에서 P까지의 경로 중 위 세 점을 지나는 경우는 각각 1², 2², 3²이고, 덧셈 법칙에 의해 총 14가지라는 걸 알 수 있죠.

P에서 B까지의 경로도 마찬가지로 9회차에 지날 수 있는 점들을 기준으로 세어보면 $2^2+4^2+1^2+1^2=22$가지예요. 즉, 구하고자 하는 경우의 수는 308이 되죠.