출근길

1. 문제

지루해 씨는 매일 아침 집에서 회사까지 걸어서 출근한다.

회사에 지각하면 안 되는 지루해 씨는 항상 최단 경로를 고려한다.

아래 [그림 1]은 지루해 씨의 동네 지도다.

지루해 씨가 사는 동네는 곳곳에서 공사를 하고 있는데, 공사 중인 곳은 지나갈 수 없다.

왼쪽 위의 집에서 출발하여 오른쪽 아래의 회사에 도착해야 한다.

[그림 1]

Q. 출근길의 수

지루해 씨가 출근길로 택할 수 있는 경로는 모두 몇 가지인가?

 

2. 문제 분석

직관론적으로 조합을 이용해서 경우의 수를 구해볼 수 있다.

그러나, 우리는 컴퓨터 사고 방식으로 문제를 해결해야 한다.

이 문제를 해결하는 핵심은 다음과 같다.

출발점에서 각 지점까지 갈 수 있는 경우의 수를 적어나간다.

먼저, 가장 위의 도로, 가장 왼쪽 도로에 경우의 수를 적는다.

공사 중인 곳을 제외하고, 모두 한 가지 경로가 있다.

그 다음 각 지점마다 그 지점까지 갈 수 있는 최단 경로의 수를 적어 나간다.

위에서 내려오는 경우와 왼쪽에서 오는 경우를 더한다.

만약, 위쪽이나 왼쪽이 공사 중이면 더하지 않는다.

이처럼 계속 적어 나간다. 도착점까지 다 채우면 총 53가지 출근길이 있음을 알 수 있다.

먼저, 경우의 수를 적어보자.

[그림 2]

[그림 3]

 

3 - (1). 재귀함수를 이용한 구현

위의 방식은 동적 프로그래밍의 방법이다.

구현 방식은 DFS를 이용한 방법을 구하도록 한다.

탐색할 초기위치는 (0,0)을 시작으로 (4,4)까지 탐색을 하는데 탐색할 방향은 총 2가지이다.

오른쪽 혹은 아래쪽이다.

이는 점화식으로 표현을 할 수 있는데, 말로 설명하면 다음과 같다.

현재의 위치를 curRow, curCol이라 하면, 현재의 위치에서 끝 지점까지의 모든 경로의 가지 수는

현재의 위치에서 오른쪽 위치를 시작점으로 해서 끝 지점까지의 모든 경로의 가지 수와

현재의 위치에서 아래쪽 위치를 시작점으로 해서 끝 지점까지의 모든 경로의 가지수의 합이다.

그리고 이는 점화식으로 표현할 수 있다.

점화식으로 표현이 가능하므로 재귀함수를 이용해서 구할 수 있다.

프로그램 실행결과

소스 파일

main.c

0.00MB

 

3 - (2). 동적 프로그래밍을 이용한 구현

프로그램 실행결과

소스 파일

main.c

0.00MB