[기본개념] 최단 경로의 수

포스트내용

같은 것이 있는 순열을 이용하여 최단 경로의 경우의 수를 구하는 것을 배웁니다. 복잡하지 않은 반듯한 도형에서 쓸 수 있는 방법입니다. 그 외 순열과 조합에 관련된 강의는 이 곳을 클릭 하세요.

 먼저 예를 먼저 보겠습니가. 지점에서 지점으로 가는 최단 경로의 경우의 수는 몇 가지입니까?

1. 초등학교 방법으로 풀기

 이 문제를 해결하는데 중요한 방법은 사실은 초등학교 때 배웠습니다. 이른 바 왕수학 문제죠?

에서 로 가는 경우 최단 경로로 갈때는 그림에서 오른쪽으로 가거나 위쪽으로 갈 수 밖에 없습니다. 이를 이용하여 각 교차로에서의 경우의 수를 아래와 같이

 위처럼 교차로에서 경우의 수를 구하는 방법입니다. 각 교차로의 중심으로 도달하는 방법은 왼쪽에서 오른쪽, 아래쪽에서 위쪽으로 갈 수 밖에 없기에 위의 그림처럼 되는 것입니다. 이를 이용하여 한번 해 볼까요?

목적지 에서 가장 먼 가장자리를 중심으로 해서 경우의 수를 세어 나갑니다. 아래와 같이 각 구석의 가장자리는 1가지가 됩니다.

 그 다음 위의 방식을 이용하여

 위처럼 가 되죠? 이와 같은 방법으로 계속 시행하면 아래와  같습니다.

 위처럼 35가지가 됩니다. 아~~~ 상당히 무식한 방법이라구요? 그렇지만 이 방법은 당연하게 기본적으로 알고 있어야 합니다. 도형이 복잡해지면 급하면 이렇게 푸는 것이 가장 좋을 때도 있거든요.

2. 같은 것이 있는 순열을 이용하여 해결하기

 이제 조금 더 아방가르드~한 방법으로 하도록 하겠습니다. 아방가르드 하니까 조금 있어 보이지 않습니까? 그것은 같은 것이 있는 순열을 이용하여 해결을 하는 것인데요. 아래와 같은 아이디어로 해결하는 것입니다.

 왼쪽에서 오른쪽으로 가는 것을 라고 하고 아래에서 위로 올라가는 경우를 라고 한다면 를 일렬로 배열하면 각 배열하는 경우 각각 하나당 최단 경로가 하나씩 결정 됩니다. 예를 들어 라고 했다면 아래와 같은 경로가 완성 되는 것이죠?

 그 외의 경우도 하나씩 결정 되겠죠? 그러므로 를 일렬로 배열하는 방법의 수는 이 되는 것입니다.

예제

아래 그림과 같은 도로망이 있다.

에서 출발하여 를 경유하지 않고 로 가는 최단 경로의 수는?

풀이법1 같은 것이 있는 순열의 이용

 위의 문제를 먼저 2번 방법으로 풀겠습니다. 같은 것이 있는 순열을 이용하는 것이죠. 이 문제를 해결하는데 필요한 포인트는 아래와 같습니다.

접근 포인트 1. 여사건의 이용

 를 경유하지 않는다고 했습니다. 보통 부정의 표현이 있는 경우는 여사건을 이용하면 쉽게 해결 되는 경우가 있죠? 그래서 이 개념을 이용합니다. 즉 전체의 경우에서 로 이어지는 경우의 수를 빼면 되는 것입니다.

접근 포인트 2. 곱의 법칙의 이용

  로 가는 경우처럼 잇달아 일어나는 경우는 곱의 법칙이죠? 이를 이용하여 아래와 같이 문제를 해결 할 수 있겠네요

위의 결과를 아래의 풀이에 정리 하도록 하겠습니다.

풀이 1. 같은 것이 있는 순열의 이용

에서 로 가는 경우의 수는 가지

에서 로 가는 경우의 수는 가지

따라서, 에서 로 가는 최단 경로의 수는

가지 

따라서, 구하는 최단 경로의 수는 가지

다른 풀이법 초등 왕수학

 아 선생님 복잡한데 방금처럼 아무 생각 없이 풀 수 있는 방법은요?

 이 정도는 해야 되는데. 혹시나 시험이 너무 급한 경우는 초등학교 방법으로 해결 할 수 있습니다. 많은 학생들은 초등학교 방법을 더 좋아 하더라구요. 그래도 최대한 새로 배운 개념들을 적용할 수 있도록 위의 방법으로 연습하는 것이 좋습니다. 아무리 복잡한 도형도 일단 위의 방법을 적용하고 도저히 안 되겠다고 생각하는 사람은 생존전략으로 아래 설명하는 방법을 자신의 것으로 만들면 되겠습니다.

 문제는 아래와 같았습니다.

 여기서 를 지나지 않는다고 했으므로 는 공사중이라고 생각 합시다. 그렇다면 로 이어지는 길은 이용할 수 없습니다. 그래서 아래와 같은 그림이 완성 됩니다.

 여기서 무식하게 보이지만 초등학교 학생에게 물어 보거나 여러분들이 직접 해서 경우의 수를 구할 수 있겠죠? 초등학생한테 물어 보면 상당히 부끄럽지 않습니까? 이건 아무리 갓동주 형님께서 한점 부끄러움이 없어라고 했지만 정말 부끄러운 일이 아닐 수 없습니다.

 갓동주 형님이 누구예요?

 야. 이거 많이 했는데 윤동주 선생님 몰라?

 입새에 이는 바람에도 한점 괴로워 했던 선생님 말이야.

그래서 이것을 이용해서 아래처럼 세어 나가면 되겠죠?

 이렇게 해서 66가지가 되었습니다.

 쌤. 저는 이 방법이 더 좋은 것 같은데요?

 서연아. 그래. 그렇지만 아무 생각없이 푸는 것 복

기출문제 예제

그러면 조금은 오래 되었지만 기출문제를 하나 봅시다.

그림과 같은 바둑판 모양의 도로망이 있다. 갑은에서 까지 굵은 선을 따라 걷고, 을은에서까지 굵은 선을 따라 걸으며, 병은에서까지 도로를 따라 최단거리로 걷는다.

  갑, 을, 병 세 사람이 모두 만나도록 병이에서까지 가는 경우의 수를 구하시오.  (단, 갑, 을, 병은 동시에 출발하고 같은 속력으로 걷는다고 가정한다.)

 

이 문제를 해결할 때 갑과 을이 어떻게 움직일지 상황적인 판단이 필요하겠네요. 상황적인 판단을 하기 위해서는 문제를 해결할 때 문제에 직접 여러분이 파고 들어가야 합니다. 그래야 이 상황을 정확하게 파악 할 수 있겠죠?

갑과 을이 동시에 같은 속력으로 걷는다고 하면 어디에서 만나겠습니까? 그렇습니다. 아래 그림에서 빨간 점을 찍은 부분에서 만나게 되겠죠?

그런데 병도 같은 자리에 만나야 되므로 병도 빨간 부분을 지나야 되는 것입니다.

그렇다면 병이 지나야 되는 반드시 지나야 되는 경로는 아래와 같으므로

반드시 지나는 교차로를 점으로 찍어보면 아래와 같고 병은 반드시

병은 반드시 의 경로를 지나면 되겠죠? 그러면 로 가는 경로의 수는

위처럼 같은 것이 있는 순열을 생각하면 가지가 됩니다. 또한 에서 로 가는 경로의 수도 마찬가지로 가지 이고 로 가는 경로는 잇달아 일어나는 경우의 수이므로 곱의 법칙을 이용하면 가지가 되겠죠?