알고리즘2012. 3. 11. 23:17

장기판에서 馬 가  시작지점에서 원하는 지점까지 

최소 움직임을 보이는 경로를 찾는 문제이다.



이는 최소비용을 구한다는 점과 , 그 경로를 구한다는 점에서

DP( Dynamic Programming) 문제임을 눈치챌 수 있다.



이를 해결하기 위한 아이디어를

밑에 그림으로 설명을 하였다.

 














실제로 이 아이디어를 C언어 코드로 구현을 하였다

밑에 링크에서 코드를 볼수 있다.

http://ideone.com/QYOfU





실제로 2차원 배열에 기록을 하면서

시작지점의 값이 INF 에서 다른 값으로 변하는 순간

바로 그값이 최소비용이다. 그리고 메모라이즈 된 값들을

이용하여 값을 역추적.. 루트를 찾아낼수 있는 것이다.



Posted by 멍충한아싸

댓글을 달아 주세요

  1. 완전상미분방정식 검색했다가 좋은 글들 보고갑니다. ^^ 이제 막 컴퓨터공학과 2학년인 사람으로써 정말 멀게만 느껴지지만 열심히 하면 성대아싸님 처럼 멋지게 프로그램도 짜보고싶습니다. ㅎㅎ!! 내일도 화이팅이요!!!

    2012.03.14 00:30 신고 [ ADDR : EDIT/ DEL : REPLY ]