C언어로 구현한 Maze Problem

목차

1. 과제 목표
2. 설계
3. 결과 보고
4. 자료구조 및 알고리즘 분석
5. 전체 코드

본문내용

1. 과제 목표
- 입력된 미로의 정보를 사용하여, 미로의 경로를 탐색하는 프로그램을 완성해라

2. 설계
- 미로 탐색 알고리즘에서 주로 사용하는 자료구조는 스택으로, 스택은 입력과 삭제가 한 방향에서만 이루어지는 자료구조 입니다. 본 프로그램에서는 매번 현재 위치에서의 8방향으로의 경로를 시도하게 되는데 막다른 길에 다다랐을 시 이전에 진행했던 시점까지 돌아가야 하므로, 스택의 입출력 방식을 알맞게 적용할 수 있었습니다.

3. 결과 보고
- Input으로 주어진 maze.txt의 정보를 입력으로 사용한 결과입니다.

4. 자료구조 및 알고리즘 분석
미로의 경로를 찾는 알고리즘에서 가장 주요하게 사용한 자료 구조는 stack이며, 이 stack은 각각 현재 위치를 나타내는 row, col 그리고 방향까지의 정보를 매 칸마다 담게 됩니다. 따라서 해당 요소들을 element 구조체로 묶어 선언하였습니다. 또한 현재 위치 기준으로 8방향으로의 다음 위치 탐색 시도가 이어지므로, 각 방향으로의 위치 조정 값을 offset이라는 구조체로 선언하여 활용하였습니다. stack을 선언함과 동시에 스택의 현재 top을 가리키는 변수 또한 선언하였습니다. 2차원 배열 maze는 미로 전체의 정보를 나타내며 0은 빈 칸, 1은 벽으로 판단합니다. Mark 같은 경우는 이 알고리즘이 경로 진행 상에서 방문할 수 있는 칸은 한 번씩만 지난다는 가정 하에 이루어지므로 방문 횟수를 체크하기 위해 선언되었습니다. Exit_row와 exit_col은 도착점 위치를 나타냅니다. 경로 탐색에 앞서서 maze를 1로 초기화한 이유는, maze의 전체 크기 MAX_ROW * MAX_COL 중 사용하는 부분은 파일에서 입력된 row * col 뿐이기 때문에, 나머지 부분은 벽으로 판단하도록 해 코딩을 좀 더 쉽게 하기 위해서입니다. Mark는 방문한 위치들의 정보이므로 처음에는 모두 0으로 초기화 하였습니다.

참고자료

· 없음