검색어 입력폼

[자료구조]Knight`s tour ( 기사의 여행 )

등록일 2006.03.26 한글파일 한컴오피스 (hwp) | 6페이지 | 가격 500원

소개글

C++로 작성한 Knight`s tour ( 기사의 여행 ) 프로그램 소스화일 및 레포트입니다.

컴파일 실행환경

C++

본문내용

1. 문제개요
→ 체스에서 기사의 여행(Knight‘s tour) 이라는 것에 관한 프로그램
임의의 위치에 놓여진 기사(Knight)를 오직 한 번만 방문하면서 체스 판의 모든 위치를 방문하게 하는 프로그램을 만드는 것이 목적이다.


2. 알고리즘
→ 원래는 임의의 위치에 놓여진 기사(Knight)를 오직 한 번만 방문하면서 체스 판의 모든 위치를 방문해야 하는데, 이것은 프로그램 상 거의 불가능하다고 봐야한다. 그리하여 1823년 J.C.Warndorff가 제시한 알고리즘을 이용하여 가장 효과적인 기사의 여행 (Knight‘s tour) 프로그램을 만든다.

1) 체스 판을 만들고(8*8), 0으로 초기화 시킨다.
2-1) 기사(Knight)의 시작점을 입력받아 1로 설정한다.
2-2) 입력받는 값은 체스 판의 범위를 벗어나지 않도록 한다.
3-1) 기사가 총 이동할 횟수를 입력받는다.
3-2) 총 횟수를 대략 1~10,000정도로 제한한다.(프로그램 편의상)
4) 체스 판에 기사(Knight)의 시작점을 표시하여 출력한다.
5-1) 기사(Knight)가 갈 수 있는 8곳을 체크하여, 체스 판의 범위를 벗어나는지를 판별한다.
5-2) 체스 판의 범위 안에 있는 최소의 출구를 찾아서 방문횟수를 증가시킨다.
6) 기사(Knight)의 위치를 최소출구로 이동시킨다.
7) 5~6과정을 입력받은 총 횟수만큼 반복한다.
8) 최종결과(각각의 방문회수)가 저장된 체스 판을 출력한다.

참고 자료

없음
다운로드 맨위로