(모두의 알고리즘) 미로 찾기 알고리즘
- 미로 찾기 : 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘
- 문제 분석과 모델링
- 이 문제를 컴퓨터에게 풀어 보라고 하려면 어떻게 해야 할까?
- 사람에게는 쉽지만 컴퓨터에게 이 문제를 이해하고 풀게 하긴 어려움
- 이때 필요한 것이 바로 ‘모델링(모형화)’
- 모델링이란 주어진 현실의 문제를 정형화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명할 수 있도록 다시 표현하는 것
- 모델링은 자연이나 사회현상을 사람의 언어로 표현한 문제를 컴퓨터가 쉽게 이해할 수 있도록 수학식이나 프로그래밍 언어로 번역하는 절차
- 공간의 정형화
- 그래프로 표현
- 딕셔너리로 표현
123456789101112131415161718maze = {'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']} - 미로 찾기 소스 코드
123456789101112131415161718192021222324252627282930313233343536373839def solve_maze(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 pfor x in g[v]:if x not in done:qu.append(p + x)done.add(x)print(qu, done)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_maze(maze, 'a', 'p'))
