모델링 (모형화)
주어진 현실의 문제를 정형화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명할 수 있도록 표현하는 것
자연이나 사회현상을 사람의 언어로 표현한 문제를 컴퓨터가 이해할 수 있는 수학식이나 프로그래밍 언어로 번역하는 철차
아래와 같은 그림으로 출발점과 도착점이 주어졌을 때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 구현하라.
위 문제를 모델링하면
a에서 출발해 p로 도착하는 최단 경로를 구하고, 그 경로를 출력하라.
미로는 그래프를 이용해 정의한다. 각 위치를 꼭짓점으로, 각 위치에서 직접 연결된 위치를 선으로 하는 그래프를 정의하면 된다.
코드
maze_info = {
'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']
}
미로 찾기 알고리즘은 그래프 탐색 알고리즘을 응용한다.
def maze(graph, start, end):
q = [] # 이동 경로를 저장
done = set() # 큐에 추가된 꼭지점 저장
q.append(start)
done.add(start)
while q:
p = q.pop(0)
v = p[-1]
if v == end:
return p
for rel in graph[v]:
if rel not in done:
q.append(p + rel)
done.add(rel)
return "?"
참고 문서
728x90