[4.17] 응용 문제 1. 미로 찾기 알고리즘

모두의 알고리즘 with 파이썬 다섯째 마당 응용 문제

문제 16. 미로 찾기 알고리즘

 

1. 그래프로 모델링

그림 생략..

 

2. 딕셔너리

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

3. 출구 탐색 알고리즘

입력 : maze, 출발점 start, 도착점 end출력 : a e i m n j f g h l p(a -> p의 최단 경로)- 지나온 경로를 문자열에 저장(way += i 이용?)

 

반복을 하다가 종료 조건(?) p가 나오면 끝낸다. cf) 문제 15. 그래프 탐색 알고리즘

def find_frs(a, x):
  qu = []
  done = set()

  qu.append(x)
  done.add(x)

  while qu:
    value = qu.pop(0)
    print(value)
    for i in a[value]:
      if i not in done:
        qu.append(i)
        done.add(i)

print(find_frs(maze, 'a'))

#출력값은 : aeimnjfkbgochdlp 음.. 어떻게 바꾸지..

def find_frs(a, start, end):
  qu = []
  done = set()

  qu.append(start) #qu = [start]
  done.add(start) #done = {start}
  way = start #way = "start"

  while qu: #qu에 남아있는 동안
    if end in qu: #종료 조건을 만들어준다. 
      return way
    
    value = qu.pop()

    for i in a[value]:
      if i not in done:
        way += i
        qu.append(i)
        done.add(i)

#이 상태에서는 불필요한 'kob'가 way에 있음.

print(find_frs(maze, "a", "p"))

모르겠다...

#예제 코드
def solve_maze(maze, start, end):
  qu = []
  done = set()

  qu.append(start)
  done.add(start)

  while qu:
    p = qu.pop(0)
    v = p[-1]
    if v == end:
      return p
    for x in maze[v]:
      if x not in done:
        qu.append(p+x)
        done.add(x)
  return "?"

print(solve_maze(maze, "a", "p"))