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

1. 알고리즘

텍스트 모드에서 그래픽 문자를 이용하여 미로를 화면에 표시합니다. 미로는 2차원 배열로 미리 작성해 둔 것을 사용하며, 우측 하단에서 출발하여 좌측 상단에 도착하는 것을 목표로 합니다. "C로 배우는 알고리즘"^[각주:1]에 설명된 알고리즘은 우선법(right hand all wall) 방법으로 최단 경로를 계산하여 계산된 최단 경로로 다시 한번 이동하는 모습을 보입니다. 내용을 찾아서 검색하다가 유용한 링크를 찾았습니다.

• http://ddmix.blogspot.kr/2014/12/cppalgo-4-array-maze.html
• http://codingdojang.com/scode/481

2. 동작 코드

아래와 같은 상수를 정의해서 미로를 배열로 표시합니다.

UP = 1
RIGHT = 2
DOWN = 4
LEFT = 8

OR 연산을 이용해서 다양한 표현이 가능하도록, 2^0, 2^1, 2^2, 2^3으로 신경써서 정의했습니다. 이를 이용해서 벽의 모양을 표시하면 아래와 같은 표를 작성할 수 있습니다.

벽배치의 고유값	벽의 배치	벽의 모양	벽모양의 ASCII 코드
0	벽없음, 공간		32
1	UP	│	179
2	RIGHT	─	196
3	UP | RIGHT	└	192
4	DOWN	│	179
5	UP | DOWN	│	179
6	RIGHT | DOWN	┌	218
7	UP | RIGHT | DOWN	├	195
8	LEFT	─	196
9	UP | LEFT	┘	217
10	RIGHT | LEFT	─	196
11	UP | RIGHT | LEFT	┴	193
12	DOWN | LEFT	┐	191
13	UP | DOWN | LEFT	┤	180
14	RIGHT | DOWN | LEFT	┬	194
15	UP | RIGHT | DOWN | LEFT	┼	197

아래 링크들을 참고했습니다.

• http://www.theasciicode.com.ar/
• https://stackoverflow.com/questions/46063974/printing-extended-ascii-characters-in-python

기본적으로 Python으로 Extended ASCII 문자를 표현하기 어려우므로, Unicode를 이용해서 표현했습니다.

• http://svn.python.org/projects/stackless/trunk/Lib/encodings/cp720.py

그림을 그리기 위한 get_shape 함수는 다음과 같습니다.

def get_shape(m, x, y):
    shape = (u' ', u'\u2502', u'\u2500', u'\u2514', u'\u2502', u'\u2502', u'\u250c', u'\u251c', u'\u2500', u'\u2518',
             u'\u2500', u'\u2534', u'\u2510', u'\u2524', u'\u252c', u'\u253c')
    s = 0
    if m[x][y] != 0:
        # Check upper range
        if x > 0 and m[x-1][y] != 0:
            s |= UP
        # Check lower range
        if x < MAZE_SIZE - 2 and m[x+1][y] != 0:
            s |= DOWN
        # Check left range
        if y > 0 and m[x][y-1] != 0:
            s |= LEFT
        # Check right range
        if y < MAZE_SIZE - 2 and m[x][y+1] != 0:
            s |= RIGHT

    return shape[s]

그림을 그리는 실제 함수는 다음과 같습니다.

def draw_maze(m):
    for j in range(MAZE_SIZE):
        for i in range(MAZE_SIZE):
            ch = get_shape(m, i, j)
            stdscr.addstr(i+1, j+1, ch)

터미널을 사용하기 위해서 curses^[각주:2]를 이용했습니다. C언어의 gotoxy()에 해당하는 함수가 stdscr.addstr()입니다.

3. 실행 코드

위의 두 함수를 이용해서 문제에 이용하는 미로를 그리는 코드입니다. ("C로 배우는 알고리즘" 리스트 3-3 : ROBOT.C의 일부)

maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, 1, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 ,0, 0, 0, 1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

stdscr = curses.initscr()
# Clear screen
stdscr.clear()

draw_maze(maze)

stdscr.refresh()
stdscr.getkey()

윈도의 cmd창에서 위 코드를 수행하면 아래와 같은 미로 그림을 볼 수 있습니다.

다음편에서 계속하겠습니다.

1. http://www.yes24.com/24/goods/18003 [본문으로]
2. http://steadyandslow.tistory.com/99 [본문으로]