BFS로 풀 수 없을 이유는 없어 보입니다. 

코드를 올려주시니 질문이 명확해져서 답변하기 편해졌네요. 

크게 두 가지 문제가 있는데

1.  방문 체크가 없음 (visited)
2. 잘못된 자료 구조의 사용 (priority queue를 사용하는데, 우리가 실제로 구하고 싶은 턴 개수가 아닌 점수라는 다른 기준으로 정렬됨)

정도가 있는 것 같습니다. 둘 다 BFS를 올바르게 구현하지 않으셔서 생기는 문제입니다. 

상태 정의는 정확해 보이니 올바른 BFS를 구현하시면 맞으실 것 같습니다. 

말씀해주신 부분을 고심하다가 방금 겨우 해결했습니다! 

방문 체크를 어떻게 해야할 지에 대한 고민이 많았는데, 다른 공부를 하던 중에 생각나서 적용하니 PASS됐네요.. 

소중한 가르침을 받은 것 같아서 기쁘네요..  감사합니다. 

감사합니다!