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

1. 알고리즘

"C로 배우는 알고리즘"^[각주:1]에 설명된 right hand on wall 알고리즘은 다음과 같습니다.

1. 앞으로 간다.

2.아직 미로 안에 갖혀 있다면

2.1. 오른쪽으로 방향을 90도 튼다.

2.2. 만약 벽이 앞에 있다면

2.2.1 왼쪽으로 방향을 90도 튼다.

2.3 앞으로 간다.

2.4 2로 돌아감

3. 미로 탈출 성공!

2. 동작 코드

앞으로 가는 함수은 forward() 함수는 다음과 같습니다.

def forward(x, y, dir):
    # Delete mouse
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), " ")
        stdscr.refresh()

    if dir == LEFT:
        y -= 1
    if dir == RIGHT:
        y += 1
    if dir == UP:
        x -= 1
    if dir == DOWN:
        x += 1

    # Record movement of mouse
    record(x, y)

    # Draw mouse
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), ROBOT)
        stdscr.refresh()

    return x, y

책과는 달리 x와 y를 바꿔서 진행했습니다. TERMINAL 변수는 윈도우의 cmd창에서 진행할때는 '1'로, PyCharm에서 컴파일이나 기타 Debugging을 할때 '0'으로 설정했습니다.

Right hand on wall을 실제로 구현한 right_hand() 함수는 다음과 같습니다.

def right_hand(m, x, y, dir):
    if TERMINAL:
        stdscr.addstr(x + 1, 2*(y + 1), ROBOT)
        stdscr.refresh()
        time.sleep(0.1)

    # Record movement of mouse
    record(x, y)

    x, y = forward(x, y, dir)
    while still_in_maze(x, y):
        # 100 ms sleep
        time.sleep(0.1)
        dir = right(dir)
        while wall_ahead(m, x, y, dir):
            dir = left(dir)
        x, y = forward(x, y, dir)

    # End of record
    record(-1, -1)

최초 start point에 마우스를 그리고, 미로에 있는 동안 forward() 함수를 계속 호출합니다. 만약 벽을 만났다면(wall_ahead() 함수) 방향을 전환(left() 함수)합니다.

여기서 mouse를 그리거나 지울때 y 좌표를 그대로 사용하지 않고, 2를 곱해서 미로의 line이 지워지는 것을 최소화했습니다.

실행되는 코드를 사람이 확인할 수 있도록 time.sleep()을 사용했습니다. 여기서 sleep()의 인자로는 "초단위" 이외에 floating으로 msec 단위도 설정할 수 있습니다.^[각주:2]

3. 실행 코드

미로를 그리고 마우스가 right hand on wall 기법으로 미로를 빠져나가는 것을 볼 수 있는 코드는 아래 링크를 참고해 주십시오. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C의 일부) 아직 "최단 경초 찾기" 코드는 추가하지 않았습니다.

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_03/Ch_03_1_1.py

다음편에서 "최단 경로 찾기"까지를 포함해서 완성해 보겠습니다.

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://hashcode.co.kr/questions/1008/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8%EC%9D%84-50-ms-sleep%ED%95%98%EB%A0%A4%EB%A9%B4-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%B4%EC%95%BC%EB%90%A0%EA%B9%8C%EC%9A%94 [본문으로]