wwww 0 bbbb를
bbbbb 0 wwww로 만드려고 합니다.
(1) 0는 구멍이고 구멍과 인접한 w 혹은 b는 swap이 가능합니다
ex) www 0 w bbbb 이런 식으로 가능합니다
(2) 또한 다른 돌이 옆에 있고 그 다음 구멍이 있을 경우 점프가 가능합니다.
ex) www b 0 w bbb 상태에서
ww0 b w w bbb 이런식으로 가능합니다.
최소한의 이동 횟수를 구하는 것이 문제인데
우선 저는 각 움직임 (1), (2)을 구현하였고
그 다음 각 상태를 string으로 만들었고 횟수와 함께 map에 저장했습니다.
그런데 n이 조금만 커지니 오버플로우가 발생하더라구요. 효율적인 방법이 혹시 있을까요?
n이 얼마이길래
n은 15까지입니다 움직인 position도 출력을 해야하는데 완전탐색으로 돌리니 오버플로가 나네요.
일단 효율적으로 저장하면 C(31, 15)로 저장가능 3*10^8 정도임. 그래도 너무 많으니까 그리디 알고리즘이 있을것
아 그런데 이거 방법이 거의 한정되어있는데?
갤주님 혹시 한정된 방법을 좀 알 수 있을까요?
해보면 알겠지만 움직일수 있는 가짓수가 적음 아마 A* 같은 방법으로 탐색하고 state는 string을 이용한 해시맵으로 저장하는게 아니라 32비트 숫자로 변경해서 저장하면 됨
링크나 키워드만 알려주시면 제가 찾아보겠습니다