어떤가요? 뭔가 조금 더 기계가 이해하기 쉬운 문제로 바뀐 것 같나요?

이제 다음 단계로 넘어갈 차례입니다. 최종 결과를 얻으려면 각 위치 사이의 관계를 컴퓨터에게 알려 줘야 하고 실제로 미로를 푸는 알고리즘도 만들어야 합니다. 여전히 어려워 보이지만 사실 이 문제는 문제 15에서 풀었던 그래프 탐색 문제와 같습니다.

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

 

그림 16-3 주어진 미로를 그래프로 표현