Project 1 – 미로 찾기

소개글

Project 1 – 미로 찾기에 대한 보고서 자료입니다.

목차

1. Algorithm

2. Issue Point

3. Conclusion

본문내용

1. Algorithm
미로 찾기 알고리즘은 이미 잘 알려져 있는 바와 같이 그래프 알고리즘을 사용하여 구현하는 것이 좋고 그 중에서도 Dijkstra 알고리즘을 써야 한다고 생각했습니다. 그래서 Dijkstra 알고리즘을 사용하여 구현하려 하였는데 결과적으로 봐서 완벽하게 그 알고리즘을 적용하지는 못한 것 같습니다. (이에 대해서는 후반부에 다시 언급하겠습니다.)
먼저 하나 하나의 블록을 표현하기 위해 s_node라는 구조체를 선언하여 사용하였습니다.
typedef struct s_node {
int loc_x, loc_y; // x 좌표, y 좌표
struct s_node *prev_node; // 이전 노드 포인터
struct s_node *next_node; // 다음 노드 포인터
} s_node_t;
위에서 보듯이 각각의 노드는 이전 노드와 다음 노드에 대한 포인터를 가지고 있는 doubly linked list 형태로 하였습니다. 처음에는 이전 노드에 대한 포인터만으로 구현하였는데, 이렇게 할 경우 최단이 아닌 경로에 대한 메모리 해제 처리가 힘들어서 양쪽에 대한 포인터를 두었습니다. 또한 자주 사용하는 상수로 PRETTY_BIG_INT를 두었습니다. 이는 (미로의 가로 * 세로 사이즈 + 1)의 크기를 가지고 있으며 논리적으로 생각했을 때 최단 경로가 될 수 없는 값이라 현재 검사하는 경로가 최단 경로가 아님을 표현하는데 사용하였습니다.
기본적으로는 다음과 같은 전제를 두고 recursive하게 다음 node를 찾는 방법을 사용하였습니다.
1. (현재 경로가 경유한 노드 수 + 현재 노드에서 출구까지 모두 뚫려있다고 가정했을 때의 앞으로의 경로 수) 가 지금까지 밝혀진 최단 경로 수보다 많다면 더 이상 이 경로에 대해 분석하지 않는다.
2. 현재 노드가 미로 지도를 벗어난다면 더 이상 분석하지 않는다.
3. 입구에서 현재 노드까지 오는 경로수가 지금까지 밝혀낸 이 노드로 오는 최단 경로 수보다 많거나 같다면 더 이상 분석하지 않는다. 반대의 경우는 이 노드까지의 최단 경로 수를 업데이트한다.

키워드

미로,   maze,   미로 찾기