자기 자신을 방문한 자신의 직전 타일을 가리키는 배열을 하나 두면 됩니다.

BFS로 탐색하면서 이 배열을 업데이트 해주고

끝난 후 직전 타일 경로를 거꾸로 따라가면 

처음 타일까지 가는 역경로를 알 수 있고 이를 거꾸로 하면 원하는 경로를 알 수 있습니다.