dladydwo123   5년 전

제목 그대로 입니다. 처음에 단순하게 생각했을 때, 미친로봇의 움직임은 4가지로서 최악의 경우 움직일 수 있는 경우는 4^14 이라고 생각했습니다. 

방문 테이블을 이용해서 지나왔던길에 또 들르게 돼면 끝나게 된다 할지라도, 이 경우를 지운다 해도 총 조사하는 경우는 3^13 * 4아닙니까?

( 3^13 * 4 라 함은, 단순움직임을 방지하기위해서, 전에 'E'로 움직였다면 단순 움직임이 가능하게 하기위해 W을 제외한 움직임이 3가지. 이를 처음 빼곤 모두 똑같음으로 13번 곱해서, 해당 경우를 생각했습니다.)

결국 시간내에 못풀 꺼 같다고 생각했는데, 방법론은 이 방법외엔 떠오르지 않고... 

궁금합니다.


seico75   5년 전

full search 를 하면 그렇게 되겠지만, 방문테이블로 단순움직임이 아니라는 것을 판단하게 된다면 중단하여 전체 처리하는 것은 저것보다는 적을 것 같습니다.

예를 들어 ESWNEEEEEWWWWNNNNNEE  이런 입력을 처리하려고 하면 4번째에서 두번 방문하는 곳이 발생하니 그 이후의 경우들 4^10 혹은 3^10 의 경우를 절약하지 않을까요?

댓글을 작성하려면 로그인해야 합니다.