출근길은 즐거워

1. 문제

이번에는 출근길에 주위 경치의 아름다움을 느낄 줄 아는 즐거워 씨의 이야기이다.

즐거워 씨는 동네의 각 위치마다 아름다운 정도를 나타내는 자연수 값을 적어두고 있다.

아름다운 정도를 나타내는 즐거워 씨의 동네 지도는 다음의 2차원 배열로 나타낼 수 있다.

즐거워 씨의 동네에는 공사 중인 곳이 없다.

[그림 1]

즐거워 씨도 매일 아침, 위치 (0,0)에서 위치 (4,4)로 출근한다.

즐거워 씨가 출근길에 느끼는 즐거움은 지나가면서 만나는 경치의 아름다움의 합이 된다.

예를 들어, 아래의 [그림 2]와 같이 출근하면 1+1+2+1+3+1+2+1+2 = 14 만큼의 즐거움을

느끼며 출근하게 된다.

[그림 2]

즐거워 씨도 항상 최단 거리로 출근한다.

예를 들어, 아래 [그림 3]과 같은 경로는 매우 즐겁긴 하겠지만, 지각할 수 있으므로

출근길이 될 수 없다.

[그림 3]

Q. 프로그램 작성하기.

즐거워 씨가 출근길에 즐기는 경치의 아름다움의 총합은 최대 얼마까지 가능한지 알려주는

프로그램을 작성하라.

 

2 - (1). DFS 구현

프로그램 실행결과

소스 파일

main.c

0.00MB

 

2 - (2). 동적 프로그래밍 - 가중치

프로그램 실행결과

소스 파일

main.c

0.00MB

2 - (3). 동적 프로그래밍 - 가중치 & 이동 경로

위의 과정까지만 해도 충분하다.

시작점에서부터 목적지까지의 이동한 경로를 출력하기 위해서는

구조체를 하나 정의 하는데, 이는 다음과 같다.

맵에 대한 정보가 이차원 배열이므로 행과 열 정보를 하나로 묶는 구조체.

그리고, 자료구조 중에서 스택이 필요하다.

그 이유는 탐색 방향이 목적지점을 시작으로 탐색할 것이기 때문이다.

즉, 스택의 맨 아래에 저장된 데이터는 목적지점이고,

맨 위에 저장된 데이터는 시작점이 된다.

그리고, 방향의 정보를 저장할 이차원 배열을 하나 정의 한다.

동적 테이블에 가중치 정보가 저장이 될 때, 방향의 정보를 구하도록 한다.

모든 탐색이 끝난 이후에, 이 방향 정보를 가지고 이동한 경로를 구한다.

위의 동적 테이블의 내용을 바탕으로 구현한다.

프로그램 실행결과

헤더 파일 & 소스 파일

common.h

0.00MB

main.c

0.01MB

MyStack.c

0.00MB

MyStack.h

0.00MB

point.h

0.00MB