[알고리즘] 미로 찾기

문제 16. 미로 찾기

Q. 다음 그림과 같이 미로의 형태와 출발점과 도착점이 주어졌을 때, 

출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 만들어보세요.

 

 

해당 문제를 풀기 위해선, 정형화 하거나 단순화하는 모델링이 필요하다.

즉, 컴퓨터 프로그램으로 쉽게 설명 할 수 있도록 다시 표현하는 것.

 

미로안의 공간을 정형화 시킨 모습은 아래와 같다.

 

 

 

 

---

 

 

 

 

4x4로 구성된 미로에 이동 가능한 위치를 각각의 구역으로 나누고, 구역마다 알파벳으로 이름을 붙인 모습.

 

이 모델을 이용해서 도착점 p에 이르는 가장 짧은 경로를 구해보면 답은 aeimnjfghlp 이다.

 

이 문제는 그래프 탐색문제와 비슷하기 때문에 아래와 같은 방법으로 접근하면 된다.

 

 

 

 

 

 

---

 

 

 

위치 16개를 각각의 꼭지점으로 만들고, 각 위치에서 벽으로 막히지 않아 이동할 수 있는 이웃한 위치를 모두 선으로 연결하면 그림과 같은 그래프로 만들어진다.

 

 

---

 

 

마지막으로 이 그래프를 딕셔너리 구조로 바꾸면 위와 같다.

 

---

 

처음에 그림으로 주어졌던 미로 찾기 문제가 모델링을 통해 그래프가 되고, 그 그래프가 파이썬 언어가 이해할 수 있는 딕셔너리로 표현되어 있다. 

그래프 탐색 알고리즘을 적용하여 출발점부터 도착점까지 탐색하는 프로그램을 만들면 아래와 같다.

 

 

 

 

---

 

 

출처: 모두의 알고리즘 with 파이썬