자료구조 알고리즘을 이용해 미로 탐색 알고리즘을 만들고 MST PRIM 알고리즘을 적용해 최소 신장 트리 경로를 구하기 (C 소스 포함, C source)

소개

미로를 설계한 후 최적의 경로를 찾아내는 프로그램입니다.
누구나 쉽게 알수 있도록 논문 형식 목차와 주석을 신경써서 만들었으며 C언어 소스를 첨부했습니다.
자료구조에 나오는 거의 모든 개념이 다 포함되며 이것들을 이용해서 만들었습니다.
아래 목차를 참조해주세요.

목차

1. 서론

2. 본론
1) 미로설계
2) 미로탐색 함수 설계
3) 순환과 스택을 이용한 탐색함수 구현
4) 미로탐색 결과를 시각적으로 표현하는 함수구현
5) 미로탐색경로를 바탕으로 Prim함수 만들기
6) 가중치 인접행렬 만들기
7) 가중치 인접행렬 만들고 출력하기
8) 미로경로를 연결리스트 방식으로 출력하기
9) 연결리스트 생성
10) 가중치인접행렬을 연결리스트로 전환하기
11) 순환을 이용한 연결리스트 출력
12) Prim 함수 만들기

3. 결 론

본문내용

요약미로탐색 알고리즘은 기본적인 시행착오 방법으로써 현재의 경로가 실패할 경우를 대비해서 가능한 경로들을 미리 저장되어야 한다. 이 방법으로 스택을 이용해 현재 위치에서 갈 수 있는 좌표를 스택에 저장해 막다른 길을 만나면 가장 가깝고 아직 가보지 않은 좌표부터 다시 시작해서 새로운 경로를 찾는 것이다. 이는 최소신장트리 Prim 알고리즘의 각 노드를 이어주는 최소간선을 선택하는 방법과 상당히 유사하다. 이것을 이용하여 여기서는 미로설계부터 시작해서 탐색까지 해보고 탐색 결과 나온 경로를 보기 쉽게 시각화하여 출력하였다. 이것을 바탕으로 가중치 인접행렬을 작성해서 출력한 후 연결리스트 방식으로 출력을 해보았다. 마지막으로 인접행렬을 연결리스트로 자동으로 바꾸어 순환을 이용해서 그래프를 연결리스트로 출력해보고 위의 결과와 비교해 보았다.
최종적으로 미로탐색경로를 출력한다.

키워드:신장트리, 최소신장트리, 스택, 순환, 미로 탐색, Prim 알고리즘, 가중치 인접 행렬
AbstractMaze search algorithm is the basic method of trial and error. The failure of the current path in case of possible paths must be stored in advance. Using a stack that can go from its current location coordinates stored in the stack have not visited yet, the closest encounter a dead end road starting from the coordinates is to find a new path. Prim minimum spanning tree algorithm to select the minimum edge and are very similar. Using this design, starting with a maze trying to navigate the path from the search results view to easily visualize the output by. This is based on the adjacency matrix graph created by creating a linked list and prints out the way you navigate the maze path and the final output.
Key words: Spanning tree, minimum spanning tree, stack, circular, maze navigation, Prim algorithm, weighted adjacency matrix

참고자료

· 없음