최단 거리로 갈수 있는 방법은 몇가지 일까?

배한길 info.elc09@gmail.com 글쓴이의 다른 글 보기

최종수정 : 2014-06-10 10:50

여러분들은 운전을 하시면서 어느길로 가면 가장 빨리 아니면 기름을 최소로 사용하면서 갈수 있을까? 하고 생각하신적 있으실거라 생각합니다. 오늘은 저와 함께 수학적으로 A라는 도시와 B라는 도시 사이를 갈 수 있는 방법이 몇가지 인지 알아 보도록 하겠습니다.

상황은 이렇습니다. 아래 그림을 보시면 왼쪽 맨 꼭대기에 A라는 도시가 있고 맨 아래쪽에 오른쪽에 B라는 도시가 있습니다. 이 도시 사이를 차량을 이용하여 가려고 합니다. 이때 A와 B 도시 사이에 갈수 있는 방법은 몇가지 있을까요? 조건은 각각의 사거리에서 최단거리로 진행하여야 합니다. 그 말을 쉽게 하면 왔던길로는 다시 갈수 없으며, 시간을 끌기 위해서 멀리 돌아서 갈수 없다는 것입니다.

자 그럼 한 번 보겠습니다. 첫번째 그림은 보시는 바와 같이 A에서 B까지 가는 길이 단 2개 뿐입니다. 그럼 두번째 그림은 어떨까요? A에서 B까지 가는 길은 모두 6가지 선택이 있습니다. 그럼 마지막으로 세번재 그림은 어떨까요? 세번째 그림의 경우 A에서 B까지 가는 경우의 수는 모두 20가지가 됩니다. 그럼 어떻게 이렇게 쉽게 A에서 부터 B까지의 경로의 가지수를 쉽게 찾을 수 있을까요?

혹시 그림에서 힌트를 얻으셨는지 모르겠습니다. 각각의 교차로의 숫자들을 대각선으로 더하면 쉽게 답을 찾을 수 있습니다. 좀 더 자세히 말씀 드리면 그 다음 교차로까지 갈수 있는 방법은 하나밖에 없습니다. 그렇기 때문에 바깥쪽에 있는 교차로에는 1을 쓰게 됩니다. 1이 쓰여진 교차로에 대각선으로 보고 있는 교차로의 숫자를 더하면 2가 되면 대각선상에 있는 숫자 2와 1을 다시 더하면 3이 됩니다. 즉 첫번째는 각각 대각선 상의 교차로의 숫자가 1과 또다른 1이므로 이 둘을 더하면 2가 되며 이 뜻은 A지점에서 B 지점 까지 가는 길의 종류가 2가지 있다는 이야기 입니다.