UNIT 14 (응용)

미로 찾기 알고리즘

문제) 다음 그림과 같이 미로 형태의 출발점과 도착점이 주어졌을 때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 만들어라.

#미로 찾기 프로그램 (그래프 탐색)
#입력 : 미로 정보 g, 출발 start, 도착점 end
#출략 : 미로를 나가기 위한 이동 경로는 문자열, 나갈 수 없는 미로면 물음표("?")

def solve_maza(g, start, end):
    qu = []
    done = set()
    qu.append(start)
    done.add(start)

    while qu:
        p = qu.pop(0)
        v = p[-1] #문자열 인덱싱
        if v == end:
            return p
        for x in g[v]:
            if x not in done:
                qu.append(p + x)
                done.add(x)

    return "?"

maze = {
    "a": ["e"],
    "b": ["c", "f"],
    "c": ["b", "d"],
    "d": ["c"],
    "e": ["a", "i"],
    "f": ["b", "g", "j"],
    "g": ["f", "h"],
    "h": ["g", "l"],
    "i": ["e", "m"],
    "j": ["f", "k", "n"],
    "k": ["j", "o"],
    "l": ["h", "p"],
    "m": ["i", "n"],
    "n": ["m", "j"],
    "o": ["k"],
    "p": ["l"],
}
print(solve_maza(maze, "a", "p"))

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10