BFS를 이용한 길찾기

BFS라는 개념에 대해서 알아보았다. 이제 길찾기를 진행해 본다면...

 

먼저, 길이 그래프여야 하는데 지금은 Tile 이다.

 

하지만 이런 타일의 규칙을 살펴보자면 TIle은 결국 Vertex라는 생각을 할 수 있고

 

결국 길은 상,하,좌,우 로 갈 수 있어서 하나의 타일당 자신의 상하좌우로 Edge를 형성함을 알 수 있다. 

 

벽은 갈수 없으니 연결되어 있지 않다고 생각하면 된다. 따라서 이러한 개념으로 Tile에 BFS를 적용할 수 있다.

 

Tile에 BFS를 적용 해 보자.

먼저, 타일은 X,Y로 되어있어서  상,하,좌,우에 맞는 각각의 X,Y 위치를 정의해줌을 알 수 있다.

그리고 찾은 Vertex또한 2차원 배열로 구성해서 기록한다.

 

그 외 진행은 역시 전에 만들어둔 BFS 형식과 동일하다.

 

BFS가 끝날 시 parent에 갔던 정보가 담길것.

 

 

최종 목적지부터 시작 위치까지 역으로 거슬러 올라가면서 Tile의 정보를 기록해둔다.

 

그 다음? 그것을 뒤집으면 결국 시작 위치부터 끝 위치까지 가는 경로가 생김!

 

이제 만들어진 경로를 타고 가면 BFS를 이용한 길찾기 성공!