[알고리즘] 미로 최단 경로 찾기 (finding the shortest path in a maze)

앞서 올렸던 미로 내 거리 계산 알고리즘의 upgrade version이며, 

출발지점에서 종료 지점까지의 shortest distance 뿐만 아니라 shortest path까지 tracing하는 알고리즘 입니다.

1. get a maze as input in form of an array

void graph_app_maze_distance() {    uint32 maze[] = {        0, 0, 1, 1, 0,        0, 0, 0, 1, 0,        0, 0, 1, 1, 0,        0, 0, 0, 0, 0,        0, 1, 0, 1, 1,    };    uint32 maze_width = 5;    uint32 start_idx  = 20;    uint32 end_idx    = 4;    graph_app_get_maze_path(        maze, get_length(maze, maze[0]), maze_width,        start_idx, end_idx); }

2. graph_app_get_maze_distance code

1) graph_app_maze_init_paths로 입력 array에서 ‘벽’이 아닌 ‘길’에 대해서만 path_item_t type의 instance array를 생성 후 리턴

2) items를 path item의 개수 만큼 할당

3) path item array를 graph 형태로 transform하여 graph를 형성함(items)

4) start index를 시작점으로 하여 미로 찾기를 시작

1. graph_bfs_nr: distance를 계산

2. graph_get_the_shortest_path: shortest path를 계산

3. graph_reverse_path: path를 reverse 시켜 시작부터 끝까지의 길을 기록

4. graph_app_find_distance: destination까지의 거리 출력

5. graph_trace_shortest_path: start 부터 destination까지의 shortest path 출력

void graph_app_get_maze_path(uint32 *maze, uint32 maze_len, uint32 maze_width, uint32 sidx, uint32 eidx) {    uint32 num_kinds = 0, i, num_paths = 0;    uint32 num_item  = 0;    item_t *items = NULL;    char *start_coordinate = _graph_get_str_coordinate(        sidx, maze_width);    char *end_coordinate   = _graph_get_str_coordinate(        sidx, maze_width);        for (i = 0; i < maze_len; i++)        num_paths++;    path_item_t *paths = graph_app_maze_init_paths(        maze, maze_len, num_paths, maze_width, num_item);    items = (item_t *)mem_alloc(sizeof(item_t)*num_item);    memset(items, 0, sizeof(item_t)*num_item);    graph_app_transform_path_into_graph(        items, paths, maze_len, maze_width, num_item);    int start_idx = item_find_slot(        items, start_coordinate, num_item);    if (-1 != start_idx) {        stack<u32> visit_history = graph_bfs_nr(            items, num_item, start_idx);        stack<u32> reversed_path = graph_get_the_shortest_path(            items, visit_history, num_item);        queue<u32> shortest_path =            graph_reverse_path(reversed_path);        graph_app_find_distance(items, end_coordinate, num_item);        graph_trace_shortest_path(items, shortest_path);    } else {        LOGD("WRONG IDX\r\n");    }    ... }

3. BFS

BFS code is coded in non-recursive manner but it uses a queue in order to cover up.

(as you know, code in recursive is more simple and easy to see, but I used a queue to prevent stack overflow problem)

stack<u32> graph_bfs_nr(item_t *items, uint32 n, uint32 start_idx) {    uint32 i, j;    stack<u32>  visit_history;    queue<long> idx_que;    queue<long> que;    uint32 pos, distance;    adj_node_t *adj_node;    list_node_t *node;    for (i = 0; i < n; i++) {        items[i].visited  = false;        items[i].distance = 0;    }    uint32 nums = n;    idx_que.push(start_idx);    nums--;    i = 0;    while (nums) {        if (i != start_idx)            idx_que.push(i);        nums--;        i++;    }    while (!idx_que.empty()) {        i = idx_que.front();        idx_que.pop();        if (true == items[i].visited)            continue;        que.push(i);        items[i].visited  = true;        items[i].distance = 0;        while (!que.empty()) {            j = que.front();            que.pop();            distance = items[j].distance;            LOGD("%s(%u) -> ", items[j].vertex.name, distance);            visit_history.push(j);            if (RET_TYPE_FAILURE ==                items[j].adj_list->get_head_position(                items[j].adj_list, &pos))                continue;            while (1) {                node = items[j].adj_list->get_next(                    items[j].adj_list, &pos);                if (NULL == node)                    break;                adj_node = (adj_node_t *)node->data;                int k = item_find_slot(                    items, adj_node->vertex->name, n);                if (false == items[k].visited) {                    items[k].distance = distance + 1;                    items[k].visited  = true;                    que.push(k);                }            }        }    }    return visit_history; }