파이썬 모델링 그래프 알고리즘 미로 찾기 #14

#지난 포스팅 보러 가기#

2020/03/13 - [DB엔지니어가 공부하는 python] - 파이썬 그래프 알고리즘 친구의 친구 찾기 #13

파이썬 그래프 알고리즘 친구의 친구 찾기 #13

파이썬 그래프 알고리즘 친구의 친구 찾기 #13 안녕하세요. 친구 관계를 이용해서 어떤 한 사람이 직, 간접적으로 아는 모든 친구를 출력하는 알고리즘을 공부해 보겠습니다. 우리가 요즘 하는 SNS들을 보면 친구..

stricky.tistory.com

안녕하세요.

오늘 포스팅할 파이썬 알고리즘은 모델링 그래프를 이용한 미로 찾기 알고리즘입니다.

아래와 같은 미로에서 출발지로부터 도착지로 가는 최단 경로 알고리즘을 만들어 보겠습니다.

위와 같은 미로 찾기 문제가 있다면 여러분들은 연필도 들기 전에 눈으로 이미 문제를 풀었을 겁니다.

바로 이렇게 말이죠!

하지만 우리의 계획은 우리가 문제를 푸는 것이 아니죠?

컴퓨터에게 이 미로 찾기를 풀어보라고 해야 합니다.

이때 필요한 것은 바로 '모델링 (모형화)'입니다. 주어진 현실의 문제를 정형화하거나 단순화시켜 수학을 이용하거나 컴퓨터가 프로그램을 이용하여 문제를 풀 수 있게 해 줍니다.

무슨 말일까요?

위 미로를 가로, 세로 각각 4등분을 합니다. 그리고 각 영역에 알파벳을 써줍니다. 그럼 아래와 같은 그림이 될 것입니다.

이 모델(모형)을 이용해서 정답을 다시 찾아보겠습니다.

정답 : aeimnjfghlp

이런 식으로 문제를 푼다면 컴퓨터가 사람 대신 미로를 찾아 줄 수 있을 것 같지 않습니까?

이젠 위 그림을 아래와 같이 전 시간에 공부했던 그래프로 만들어 보겠습니다.

그래프로 위 미로를 표현한다면 아래와 같을 겁니다.

그리고 위 그래프를 다시 파이썬 딕셔너리로 변경해보도록 하겠습니다.

maze = {
	'a' : ['e'],
    'b' : ['c','f'],
    'c' : ['b','d'],
    'd' : ['c'],
    'e' : ['a','i'],
    'f' : ['b','g','j'],
    'g' : ['f','h'],
    'h' : ['g','l'],
    'i' : ['e','m'],
    'j' : ['f','k','n'],
    'k' : ['j','o'],
    'l' : ['h','p'],
    'm' : ['i','n'],
    'n' : ['m','j'],
    'o' : ['k'],
    'p' : ['l']
}

처음 주어졌던 미로 찾기 문제를 모델링을 하고, 모델링한 것이 그래프가 되고, 그래프가 파이썬의 딕셔너리로 변형되어 이젠 문제를 컴퓨터가 풀 수 있게 되었습니다.

파이썬 소스로 풀이를 해보겠습니다.

# 미로 찾기 프로그램(그래프 탐색)
# 입력: 미로 정보 g, 출발점 start, 도착점 end
# 출력: 미로를 나가기 위한 이동 경로는 문자열, 나갈 수 없는 미로면 물음표("?")

def solve_maze(g, start, end):
    qu = []       # 기억 장소 1: 앞으로 처리해야 할 이동 경로를 큐에 저장
    done = set()  # 기억 장소 2: 이미 큐에 추가한 꼭짓점들을 집합에 기록(중복 방지)

    qu.append(start)  # 출발점을 큐에 넣고 시작
    done.add(start)   # 집합에도 추가

    while qu:           # 큐에 처리할 경로가 남아 있으면
        p = qu.pop(0)   # 큐에서 처리 대상을 꺼냄
        v = p[-1]       # 큐에 저장된 이동 경로의 마지막 문자가 현재 처리해야 할 꼭짓점
        if v == end:    # 처리해야 할 꼭짓점이 도착점이면(목적지 도착!)
            return p    # 지금까지의 전체 이동 경로를 돌려주고 종료
        for x in g[v]:  # 대상 꼭짓점에 연결된 꼭짓점들 중에
            if x not in done:     # 아직 큐에 추가된 적이 없는 꼭짓점을
                qu.append(p + x)  # 이동 경로에 새 꼭짓점으로 추가하여 큐에 저장하고
                done.add(x)       # 집합에도 추가함

    # 탐색을 마칠 때까지 도착점이 나오지 않으면 나갈 수 없는 미로임
    return "?"

# 미로 정보
# 미로의 각 위치에 알파벳으로 이름을 지정
# 각 위치에서 한 번에 이동할 수 있는 모든 위치를 선으로 연결하여 그래프로 표현
maze = {
    'a': ['e'],
    'b': ['c', 'f'],
    'c': ['b', 'd'],
    'd': ['c'],
    'e': ['a', 'i'],
    'f': ['b', 'g', 'j'],
    'g': ['f', 'h'],
    'h': ['g', 'l'],
    'i': ['e', 'm'],
    'j': ['f', 'k', 'n'],
    'k': ['j', 'o'],
    'l': ['h', 'p'],
    'm': ['i', 'n'],
    'n': ['m', 'j'],
    'o': ['k'],
    'p': ['l']
}
print(solve_maze(maze, 'a', 'p'))

알고리즘은 지난 시간 그래프 탐색 알고리즘과 완전히 같은 알고리즘이라고 할 수 있습니다.

그래프 탐색 과정에서 지나온 경로를 문자열로 만들어 큐에 추가하고, 목적지에 도착하면 탐색을 멈추도록 한 것입니다.

이해가 되시나요?