[Python] 미로 찾기 (Stack)

📌 What to do?

주어진 미로 파일을 이용하여 미로를 탈출하는 프로그램을 작성한다.

⚡️ 조건

• 미로의 탈출구는 스택을 이용하여 탐색하도록 한다.
• 스택을 이용할 때 마다 스택에서 어떤 정보를 PUSH하고 POP 하는지 화면에 표시하도록 한다.
• 길은 여러개가 존재 할 수 있는데, 발견한 모든 길을 화면에 표시한다.
• 추가로 길찾기에 앞서 미로를 어떻게 저장할 것인지 부터 생각한다.

완성된 프로그램의 실행 예시는 다음과 같다.

그럼 이제 내가 작성한 프로그램에 대해 설명해보겠다.

📌 알고리즘

1. 미로 저장 방식

미로의 벽을 구성하는 요소들(‘+’, ‘|’, ‘-‘)은 그대로 놔두고
길에 해당하는 부분, 즉 공백 부분만 ‘0’으로 변환하여 리스트 형태로 저장하였다.
리스트 형태로 저장한 이유는 경로의 각 점들을 하나의 좌표로 취급하여 좀 더 직관적인 사고가 가능하게 하기 위함이다.

2. 어떻게 출구까지 찾아 갈 것인가?

1) 우선 이동시의 우선순위를 부여하였다 : '아래 -> 오른쪽 -> 위 -> 왼쪽' 순으로
2) 우선순위에 맞춰 시작지점에서 출발하여 ‘0’으로 표시된 지점을 따라 이동한다.
이때 내가 지난 길은 값을 ‘1’로 바꿔준다. (내가 이미 지난 길임을 표시해주기 위해)
3) 그러다 갈림길을 만나면 이를 ‘2’로 표시해주고 여기서도 마찬가지로 우선순위에 따라 이동할 방향을 결정한다.
이때 해당 지점의 좌표와 해당 지점에서의 이동 방향(ex. D(하), R(우) U(상) L(좌))을 스택에 push해준다.
4) 갈림길에서 내가 선택한 길이 막다른 길에 다다를 경우 그곳에서 가장 가까운 갈림길의 좌표,
즉 스택의 top을 pop하여 해당 지점까지 되돌아간다.
5) 갈림길로 되돌아온 후 이전에 이동했던 방향이 아닌 다른 방향으로 다시 탐색을 시작한다.
그리고 이럴 경우 갈림길의 두 방향을 모두 탐색하게 된 것이므로 이 또한 갈림길의 좌표와 함께 스택에 다시 push해준다.
(예를 들어 갈림길에서 처음엔 아래쪽으로 이동했는데 이번엔 오른쪽으로 이동할 경우엔 ‘DR’과 같이 표기해준다.)
6) 1~5의 과정을 반복하며 출구가 나올 때 까지 미로를 탐색한다.

3. 출구에 도착하였을 때

1) 우선 첫번째 경로를 찾았으므로 경로의 개수를 나타내는 변수 path에 +1을 해준다.
2) 그리고 첫번째 경로가 표시된 미로를 출력하여 보여준다.
3) 그후 스택이 완전히 빌 때까지 스택의 요소들, 즉 갈림길들을 차례로 pop한다.
그리고 해당 지점들로 이동해가며 시작점으로 되돌아간다.

4. 시작점으로 되돌아왔을 때

시작점이 갈림길일 경우, 처음에 이동했던 방향과 다른 방향으로 이동하여 미로를 다시 탐색하며 새로운 경로를 찾는다.
시작점이 아닐 경우엔, 미로를 모두 탐색한 것이므로 프로그램을 종료 시킨다.

5. 전체 프로그램을 종료하는 방식

만약 시작점이 갈림길이라면,
스택이 두 번째로 비었을 때(empty상태가 되는 경우가 두 번 발생하였을 때) 프로그램을 종료하도록 한다.
갈림길이 아닐 경우엔
스택이 첫번째로 비었을 때(empty상태가 되는 경우가 한 번 발생하였을때) 프로그램을 종료하도록 한다.

📌 Code 설명

🛠 move_D( ), move_R( ), move_U( ), move_L( )

# 아래로 움직이게 해주는 함수
def move_D(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i + 2][j] == '0':
        # 갈림길은 '2'로 마크하고
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        # 스택에 push 해준 후
        st.push([[i + 1, j], 'D'])
        # 다음 좌표로 이동한다
        i += 1
    # 갈림길(D, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 2][j] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        st.push([[i + 1, j], 'D'])
        i += 1
    # 갈림길(R, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 1][j + 1] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, R)" % (i + 1, j))
        st.push([[i + 1, j], 'R'])
        i += 1
    # 갈림길이 아닐때
    else:
        maze[i + 1][j] = '1'
        i += 1
    return i, j

각각 현재 위치를 기준으로 아래, 오른쪽, 위, 왼쪽으로 이동하게 해주는 함수이다.
이때 내가 지나온 부분은 값을 ‘0’에서 ‘1’로 바꿔준다.
그리고 갈림길의 경우엔 ‘2’로 바꿔주고 해당 지점의 좌표와 이동 방향을 스택에 push해주고 그 내역을 출력하여 보여준다.
(ex. 갈림길의 좌표가 (14, 6)이고 갈림길에서의 이동 방향은 아래일 경우, [ [14, 6], ‘D’]를 스택에 push해준다.)

🛠 return_to_Fork( ):

# 막다른 길에서 갈림길까지 돌아가는 함수
def return_to_Fork(i, j):
    # 가장 최근에 거쳐왔던 갈림길을 스택으로부터 pop
    fork = st.pop()
    print("POP(%d, %d, %s)" % (fork[0][0], fork[0][1], fork[1]))
    x = fork[0][0]
    y = fork[0][1]
    # 갈림길에 닿을 때 까지 지나왔던 경로를 지워주며 이동
    while not (i == x and j == y):
        # 1. 아래로 이동
        if maze[i + 1][j] == '1' or maze[i + 1][j] == '2':
            maze[i][j] = '0'
            i += 1
        # 2. 오른쪽으로 이동
        elif maze[i][j + 1] == '1' or maze[i][j + 1] == '2':
            maze[i][j] = '0'
            j += 1
        # 3. 위로 이동
        elif maze[i - 1][j] == '1' or maze[i - 1][j] == '2':
            maze[i][j] = '0'
            i -= 1
        # 1. 왼쪽으로 이동
        elif maze[i][j - 1] == '1' or maze[i][j - 1] == '2':
            maze[i][j] = '0'
            j -= 1
    return i, j, fork

미로를 탐색하는 과정에서 막다른 길에 다다르거나 출구에 도착하였을 때, 해당 지점에서 가장
가까운 갈림길의 정보(좌표)를 스택으로부터 꺼내어 해당 지점으로 되돌아가게 해주는 함수이다.
이때 내가 지나왔던 경로는 다시 ‘0’으로 초기화 시켜준다.

📌 실행결과

📌 전체코드

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def isEmpty(self):
        return len(self.items) == 0

f = open('maze2.txt', 'r')
maze = []                       # 미로의 정보를 담을 리스트
line = f.readline().strip()     # 첫 줄 생략

# 미로 정보 저장
while True:
    line = f.readline().strip()                 # 파일의 정보를 한 줄씩 가져 온다
    if line == '': break
    str = line.replace(' ', '0', len(line))     # ' '는 '0'으로
    maze.append(list(str))                      # 변경하여 미로의 정보를 저장

f.close()

# 미로를 출력해주는 함수
def print_Maze(maze):
    for k in maze:
        temp1 = ''.join(k).replace('0', ' ', len(k))
        temp2 = temp1.replace('1', '*', len(k))
        temp3 = temp2.replace('2', '*', len(k))
        print(temp3)

print_Maze(maze)

# 아래로 움직이게 해주는 함수
def move_D(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i + 2][j] == '0':
        # 갈림길은 '2'로 마크하고
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        # 스택에 push 해준 후
        st.push([[i + 1, j], 'D'])
        # 다음 좌표로 이동한다
        i += 1
    # 갈림길(D, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 2][j] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        st.push([[i + 1, j], 'D'])
        i += 1
    # 갈림길(R, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 1][j + 1] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, R)" % (i + 1, j))
        st.push([[i + 1, j], 'R'])
        i += 1
    # 갈림길이 아닐때
    else:
        maze[i + 1][j] = '1'
        i += 1
    return i, j
# 오른쪽으로 움직이게 해주는 함수
def move_R(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i][j + 2] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j + 1))
        j += 1
    # 갈림길(U, R)
    elif maze[i - 1][j + 1] == '0' and maze[i][j + 2] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'R'])
        print("PUSH(%d, %d, R)" % (i, j + 1))
        j += 1
    # 갈림길(U, D)
    elif maze[i + 1][j + 1] == '0' and maze[i - 1][j + 1] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j + 1))
        j += 1
    # 갈림길이 아닐때
    else:
        maze[i][j + 1] = '1'
        j += 1
    return i, j
# 위로 움직이게 해주는 함수
def move_U(i, j):
    # 갈림길(U, R)
    if maze[i - 1][j + 1] == '0' and maze[i - 2][j] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'R'])
        print("PUSH(%d, %d, R)" % (i - 1, j))
        i -= 1
    # 갈림길(U, L)
    elif maze[i - 1][j - 1] == '0' and maze[i - 2][j] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'U'])
        print("PUSH(%d, %d, U)" % (i - 1, j))
        i -= 1
    # 갈림길(R, L)
    elif maze[i - 1][j - 1] == '0' and maze[i - 1][j + 1] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'R'])
        print("PUSH(%d, %d, R)" % (i - 1, j))
        i -= 1
    # 갈림길이 아닐때
    else:
        maze[i - 1][j] = '1'
        i -= 1
    return i, j
# 왼쪽으로 움직이게 해주는 함수
def move_L(i, j):
    # 갈림길(D, L)
    if maze[i + 1][j - 1] == '0' and maze[i][j - 2] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j - 1))
        j -= 1
    # 갈림길(U, L)
    elif maze[i - 1][j - 1] == '0' and maze[i][j - 2] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'U'])
        print("PUSH(%d, %d, U)" % (i, j - 1))
        j -= 1
    # 갈림길(U, D)
    elif maze[i - 1][j - 1] == '0' and maze[i + 1][j - 1] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j - 1))
        j -= 1
    # 갈림길이 아닐때
    else:
        maze[i][j - 1] = '1'
        j -= 1
    return i, j

# 막다른 길에서 갈림길까지 돌아가는 함수
def return_to_Fork(i, j):
    # 가장 최근에 거쳐왔던 갈림길을 스택으로부터 pop
    fork = st.pop()
    print("POP(%d, %d, %s)" % (fork[0][0], fork[0][1], fork[1]))
    x = fork[0][0]
    y = fork[0][1]
    # 갈림길에 닿을 때 까지 지나왔던 경로를 지워주며 이동
    while not (i == x and j == y):
        # 1. 아래로 이동
        if maze[i + 1][j] == '1' or maze[i + 1][j] == '2':
            maze[i][j] = '0'
            i += 1
        # 2. 오른쪽으로 이동
        elif maze[i][j + 1] == '1' or maze[i][j + 1] == '2':
            maze[i][j] = '0'
            j += 1
        # 3. 위로 이동
        elif maze[i - 1][j] == '1' or maze[i - 1][j] == '2':
            maze[i][j] = '0'
            i -= 1
        # 1. 왼쪽으로 이동
        elif maze[i][j - 1] == '1' or maze[i][j - 1] == '2':
            maze[i][j] = '0'
            j -= 1
    return i, j, fork

st = Stack()
maze[1][1] = '2'

path = 0    # 미로를 빠져 나갈 수 있는 경로의 개수
i = 1       # 좌표(행)
j = 1       # 좌표(열)
flag = 0    # 무한 루프를 빠져 나올 때 사용될 flag

# 미로가 갈림길이 아닐 경우 flag에 +1
if (maze[2][1] == '0' and maze[1][2] != '0') or (maze[2][1] != '0' and maze[1][2] == '0'): flag += 1

# 시작점에서 이동할 방향 표시
if maze[2][1] == '0':
    st.push([[1, 1], 'D'])
    print("PUSH(1, 1, D)")
elif maze[1][2] == '0':
    st.push([[1, 1], 'R'])
    print("PUSH(1, 1, R)")

while True:
    # 출구에 도착했을 때
    if i == len(maze)-2 and j == len(maze[0])-2:
        # 경로 개수 1 증가
        path += 1
        print(' ')
        # 경로가 표시된 미로 출력
        print("<Path %d>" % path)
        print_Maze(maze)
        print(' ')
        # 왔던 길을 따라 시작점까지 되돌아간다
        while not st.isEmpty():
            # 갈림길까지 돌아감
            i, j, fork = return_to_Fork(i, j)
        # 처음 시작점에서 아래쪽으로 이동했었다면
        if fork[1] == 'D':
            # 오른쪽으로 이동하여 미로 다시 탐색하기
            if maze[i][j + 1] == '0':
                st.push([[i, j], 'DR'])
                print("PUSH(%d, %d, DR)" % (i, j))
                i, j = move_R(i, j)

    # 이동이 가능할 때
    # 1. 아래로 이동
    elif maze[i+1][j] == '0':
        i, j = move_D(i, j)
    # 2. 오른쪽으로 이동
    elif maze[i][j+1] == '0':
        i, j = move_R(i, j)
    # 3. 위로 이동
    elif maze[i-1][j] == '0':
        i, j = move_U(i, j)
    # 1. 왼쪽으로 이동
    elif maze[i][j-1] == '0':
        i, j = move_L(i, j)

    # 막다른 길일때
    else:
        # 막다른 길 직전의 갈림길로 돌아간다
        i, j, fork = return_to_Fork(i, j)
        # 직전 갈림길에서 아래쪽으로 이동했었다면
        if fork[1] == 'D':
            if maze[i][j + 1] == '0':
                st.push([[i, j], 'DR'])
                print("PUSH(%d, %d, DR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'DU'])
                print("PUSH(%d, %d, DU)" % (i, j))
                i, j = move_U(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'DL'])
                print("PUSH(%d, %d, DL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 오른쪽으로 이동했었다면
        elif fork[1] == 'R':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'RD'])
                print("PUSH(%d, %d, RD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'RU'])
                print("PUSH(%d, %d, RU)" % (i, j))
                i, j = move_U(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'RL'])
                print("PUSH(%d, %d, RL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 위쪽으로 이동했었다면
        elif fork[1] == 'U':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'UD'])
                print("PUSH(%d, %d, UD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i][j+1] == '0':
                st.push([[i, j], 'UR'])
                print("PUSH(%d, %d, UR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'UL'])
                print("PUSH(%d, %d, UL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 왼쪽으로 이동했었다면
        elif fork[1] == 'L':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'LD'])
                print("PUSH(%d, %d, LD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i][j+1] == '0':
                st.push([[i, j], 'LR'])
                print("PUSH(%d, %d, LR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'LU'])
                print("PUSH(%d, %d, LU)" % (i, j))
                i, j = move_U(i, j)

    # 스택이 비게 될 경우 flag에 +1을 해준다
    if st.isEmpty(): flag += 1
    # flag가 2가 될 경우, 프로그램을 종료 시킨다
    if flag == 2: break

print(' ')
print("경로의 수 : %d" %path)