[ALGORITHMS]문제 16 미로 찾기 알고리즘

문제 16

미로 찾기 알고리즘

다음 그림과 같이 미로의 형태와 출발점과 도착점이 주어 졌을때 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 만들어보세요

1. 문제 분석과 모델링

주어진 미로는 연필을 들자마자 풀어 버릴 만큼 간단한 문제입니다.

하지만 이 문제를 컴퓨터에게 풀어 보라고 하려면 어떻게 해야 할까요?

사람에게는 정말 쉬운 문제지만 컴퓨터에게 이 문제를 이해하고 풀게 할 아이디어는 선뜻 떠오르지 않습니다.

이떄 필요 한것이 바로 모델링입니다. 모델링이랑 주어진 현실의 문제를 정혀화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명 할 수 있도록 다시  표현하는 것을 말합니다.

미로 안의 공간을 정형화 시켜보도록하겠습니다.

4x4로 구성된 간단한 미로입니다. 먼저 이동 가능한 위치를 각각의 구역으로 나누고, 구역마다 알파벳으로 이름을 붙이면 다음 그림과 같습니다.

이 모델을 이용해서 미로 찾기 문제와 정답을 다시 적어보면 다음과 같이 표현 할 수 있습니다

출발점 a에서 시작하여 벽으로 막히지 않은 위치로 차례로 이동하여 도착점 p에 이르는 가장 짧은 경로를 구하고, 그 과정에서 지나간 위치의 이름을 출력해보세요

답 : aeimnjfghlp

이제 다음 단계로 넘어가 최종 결과를 얻으려면 각 위치 사이의 관계를 컴퓨터에게 알려 줘야 하고 실제로 미로를 푸는 알고리즘도 만들어야합니다.

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

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

마지막으로 이 그래프로 딕셔너리로 바꾸면 다음과 같습니다.

2. 미로 찾기 알고리즘

처음에 그림으로 주어졌던 미로 찾기 문제가 모델링을 통해 그래프가 되고, 그 그래프가 파이썬 언어가 이해할 수 있는 딕셔너리로 표현되어있습니다. 이제 남은 일은 그래프 탐색 알고리즘을 적용하여 출발점부터 도착점까지 탐색하는 프로그램을 만드는 것입니다.

* 미로찾기 알고리즘

3. 응용문제 풀이과정

현실세계의 문제를 컴퓨터로 풀려면 문제를 분석하여 효과적인 모델을 만드는 것이 가장 중요한 첫걸음입니다.

먼저 문제를 잘 모델링하고, 그 모델에 여러가지 알고리즘을 적용하여 문제를 푼 다음 그 결과를 다시 실제세계에 적용하는 것입니다. 이는 실생황의 문제를 컴퓨터를 사용해서 푸는 일반적인 과정이기도 합니다

읽어주셔서 감사합니다