미로찾기 알고리즘 시각화

제작 동기

알고리즘 소수전공에서 배운 내용을 정리하고 응용하고자 만들게 되었습니다

배웠던것들중 길찾기 알고리즘이 가장 기억에 남아 미로찾기 알고리즘으로 주제를 정하게 되었습니다

미로 생성은..

random 과 matplotlib, networkx 이용해 미로를 생성했습니다.

총 세가지 코드를 짜서 BFS , Greedy , A 알고리즘을 시각화했습니다

BFS란

BFS는 너비 우선 탐색으로 그래프나 트리 구조에서 시작점으로부터 가까운 노드들부터 차례대로 탐색하는 알고리즘입니다.

while queue:
    current = queue.popleft()
    if current not in visited:
        visited.add(current)
        if current == goal:
            break
        for neighbor in maze[current]:
            if neighbor not in visited and neighbor not in queue:
                queue.append(neighbor)
                if neighbor not in parent:
                    parent[neighbor] = current

현재 노드를 큐에서 꺼내어 방문 집합에 추가합니다. 현재 노드가 목표에 도달하면 탐색을 종료하고, 그렇지 않다면 인접한 미방문 노드들을 큐에 추가하고 각각의 부모 노드 정보를 기록합니다. 이러한 과정을 반복하여 최단 경로를 찾습니다.

장단점 : 구현이 쉽고 최단경로를 보장합니다. 그러나 많은 노드를 저장해야 하기 때문에 맵이 커질수록 메모리 사용량이 증가할수 있습니다

Greedy 알고리즘이란

그리디 알고리즘은 매 단계에서 현재 상황에서 가장 좋아 보이는 선택을 하는 방식입니다. 이 과정을 반복해 최종 답을 만들며, 문제 해결 경로를 단계별로 결정합니다.

open_set = []
heapq.heappush(open_set, (heuristic(start, goal), start))
parent = {}
visited = set()

while open_set:
    h_val, current = heapq.heappop(open_set)
    if current in visited:
        continue
    visited.add(current)
    if current == goal:
        break
    for neighbor in maze[current]:
        if neighbor not in visited:
            heapq.heappush(open_set, (heuristic(neighbor, goal), neighbor))
            if neighbor not in parent:
                parent[neighbor] = current

시작 노드를 히유리스틱(경험에 기반한 빠른 결정 값)과 함께 우선순위 큐에 추가하고, 방문 집합과 부모 정보를 초기화합니다. 그 후 큐에서 히유리스틱 값이 가장 낮은 노드를 꺼내 목표 노드인지 확인한 후, 인접 노드들을 히유리스틱 값 기준으로 큐에 추가합니다. 목표에 도달하면 부모 정보를 통해 경로를 복원할 수 있도록 탐색을 종료합니다.

장단점: 각 단계에서 빠르고 간단하게 최선의 선택을 하므로, 구현이 쉽고 계산 속도가 빠르지만 매 단계의 선택이 전체 최적해를 보장하지 않아, 경우에 따라 전역 최적해에 도달하지 못할 수 있습니다.

A* 알고리즘은..

최단 경로를 찾기 위해 현재까지의 실제 비용과 목표까지의 예상 비용을 합한 값을 이용하는 탐색 알고리즘입니다. 각 노드에 대해 f(n) = g(n) + h(n)을 계산하여, 가장 유망한 경로를 우선적으로 탐색함으로써 효율적으로 최적 경로를 찾아냅니다.

open_set = []
heapq.heappush(open_set, (0, start))
g_score = { node: float('inf') for node in G.nodes() }
g_score[start] = 0
parent = {}
closed_set = set()

while open_set:
    f, current = heapq.heappop(open_set)
    if current in closed_set:
        continue
    closed_set.add(current)
    if current == goal:
        break
    for neighbor in maze[current]:
        tentative_g = g_score[current] + 1
        if tentative_g < g_score[neighbor]:
            g_score[neighbor] = tentative_g
            h = abs(goal[0] - neighbor[0]) + abs(goal[1] - neighbor[1])
            f_score = tentative_g + h
            parent[neighbor] = current
            heapq.heappush(open_set, (f_score, neighbor))

시작 노드로부터 g_score를 0으로 초기화하고, 우선순위 큐(open_set)에 시작 노드를 f값(0)과 함께 넣습니다. 우선순위 큐에서 f값이 가장 낮은 노드를 꺼내 목표 노드인지 확인하고, 아니라면 인접 노드들의 g_score와 f_score(= g + h)를 갱신하며 open_set에 추가합니다. 이 과정을 반복하여 목표에 도달하면, 부모 정보를 통해 최단 경로를 복원할 수 있도록 합니다.

장단점 : 휴리스틱을 활용해 최적 경로를 효율적으로 찾을 수 있으나, 휴리스틱 함수의 품질에 크게 의존하며 대규모 문제에서는 메모리 소비가 많아질 수 있습니다.

느낀점

소수전공에서 한번 배웠지만 이번기회를 통해 조금더 알아볼수 있었습니다. 시간이 많이 없어서 더 해보고 싶었던 알고리즘들을 하지 못해서 아쉬웠습니다. 2025년에는 알고리즘에 그치지 않고 다른개발도 도전해보고 싶습니다.(알고리즘 너무 힘들어요)