[03-1] 미로에 갖힌 생쥐 - 3/3

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

이상으로 "미로에 갖힌 생쥐"편을 마칩니다.