[주저리] 사천성 게임의 경로탐색

사천성(Shishen-sho) 한번쯤은 즐겨본 적이 있을 "사천성" 이라는 게임이다. 이 게임에서 가장 주된 기능이라고 하면 단연코 "경로탐색" 알고리즘일 것이다. 처음 문제에 접근할 땐 단순히 "두번이상 꺾이지 않는 경로만 탐색하면 되겠지!" 라고 생각했었는데, 이게 점차 갈수록 최적경로가 아닌 문제와 더불어 소거되는 경로를 표시하려면 좌표를 저장해야 하는데 그러한 사소한 문제부터 걸리기 시작한다. 일단 문제를 해결하기 위해서 접근가능한 방법은 아래와 같다. 1. DFS2. BFS3. Heuristic Path Finding 1. DFS(깊이-우선 탐색)가장 간단하고 직관적이다. 스택 혹은 재귀를 이용하여 다음 탐색할 대상을 찾고 거의 한쪽방향의 끝이 나올떄까지 주변을 탐색하다가, 해가 없을 경우다시 ..