Shisen-sho

문제: Shisen-sho / 조합탐색

사천성이라는 게임이 문제의 배경이고 게임 난이도를 정하는 것이 문제이다.

게임 난이도는 한 번에 없앨 수 있는 tile의 쌍으로 정해진다.

탐색의 방향이 정해져있으면 간단했을 건데 상.하.좌.우 모두 훑어봐야 하고, 중복되는 경우는 카운트 하지 말아야하기 때문에 약간 까다로웠다. 

소소한 고민.

1. 꺽어지는 경우를 어떻게 판단할까? 

문제에서는 3번 이상 방향이 전환되는 경우는 카운트하지 말아야한다고 했다. 방향 전환 유무를 어떻게 감지할까? 생각해보니 이전위치와 다음위치를 검사하면 될것같았다. 방향이 바뀌지 않았다면, 다음위치와 이전 위치가 적어도 x, y 둘 중 하나의 값은 같을 것이다. 둘다 다르다면 방향이 전환된 것이다. 그래서 재귀함수에 이전좌표를 넘겨줬다.

2. 중복해서 카운트 하는 것을 어떻게 막을까?

검사가 끝난 출발점 위치에는 '*'을 넣어줬다. (알파벳을 지운다는 의미) 더 이상 장애물이 될 뿐이라는 표시다.내가 돌아온 곳으로 못가게 하기 위해서 역시 같은 방법을 썼다.

코드: https://github.com/xgate/algospot/blob/master/SEARCH/SHISENSHO.cpp