1. 알고리즘
경로를 모두 저장한 다음, 동일한 좌표가 나오는 경우를 확인합니다. 만약 동일한 좌표가 확인되면, 일종의 jump를 한다고 생각하고, 그 사이에 있는 좌표를 모두 삭제합니다. 이후에 "최단 경로"로 동작을 합니다.
2. 동작 코드
경로를 저장하는 코드는 매우 간단하게 작성합니다.
def record(x, y):
rec.append(x)
rec.append(y)
동일한 좌표를 찾았을 때 삭제하는 코드는 다음과 같습니다.
def del_path(i, j):
k = i
while(rec[j] >=0 ):
rec[i] = rec[j]
i += 1
j += 1
rec[i] = -1
return k
최단 거리를 찾고, 다시 한번 애니메이션을 보여주는 코드는 다음과 같습니다.
def shortest_path():
i = 0
while rec[i] >= 0:
x = rec[i]
y = rec[i+1]
j = i + 2
while rec[j] >= 0:
x1 = rec[j]
y1 = rec[j + 1]
if x==x1 and y==y1:
j = del_path(i, j)
j += 2
i += 2
# Display shortest path
i = 0
while rec[i] >= 0:
x = rec[i]
y = rec[i+1]
i += 2
if TERMINAL:
stdscr.addstr(x + 1, 2*(y + 1), "*")
stdscr.refresh()
time.sleep(0.1)
stdscr.addstr(x + 1, 2*(y + 1), " ")
stdscr.refresh()
3. 실행 코드
최종적으로 미로를 그리고, right hand on wall 기법으로 출구를 찾고, 마지막으로 "최단거리"로 찾아가는 코드를 작성했습니다. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C) 아래 링크를 참고해 주십시오.
https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_1_2.py
이상으로 "미로에 갖힌 생쥐"편을 마칩니다.
반응형
'프로그래밍 > Python 초보자가 작성하는 "C로 배우는 알고리즘"' 카테고리의 다른 글
[03-5] 연결 리스트(Linked List) - 환형 연결 리스트(Circular Linked List) (0) | 2018.05.01 |
---|---|
[03-4] 연결 리스트(Linked List) - 단순 연결 리스트(Simple Linked List) (0) | 2018.04.30 |
[03-1] 미로에 갖힌 생쥐 - 2/3 (1) | 2018.04.29 |
[03-1.1] curses module (0) | 2018.04.29 |
[03-1] 미로에 갖힌 생쥐 - 1/3 (2) | 2018.04.29 |