[알고리즘] 미로 찾기
문제 16. 미로 찾기 Q. 다음 그림과 같이 미로의 형태와 출발점과 도착점이 주어졌을 때, 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘을 만들어보세요. 해당 문제를 풀기 위해선, 정형화 하거나 단순화하는 모델링이 필요하다. 즉, 컴퓨터 프로그램으로 쉽게 설명 할 수 있도록 다시 표현하는 것. 미로안의 공간을 정형화 시킨 모습은 아래와 같다. 4x4로 구성된 미로에 이동 가능한 위치를 각각의 구역으로 나누고, 구역마다 알파벳으로 이름을 붙인 모습. 이 모델을 이용해서 도착점 p에 이르는 가장 짧은 경로를 구해보면 답은 aeimnjfghlp 이다. 이 문제는 그래프 탐색문제와 비슷하기 때문에 아래와 같은 방법으로 접근하면 된다. 위치 16개를 각각의 꼭지점으로 만들고, 각 위치에서 벽으로 막..
