1405 미친 로봇

N 제한이 14로, 한 번에 동서남북 총 4가지의 방향을 움직일 수 있다. 완전탐색을 하는 4^14는 2억을 넘는 값으로 시간 안에 해결할 수 없지만 처음 이후에는 3가지 방향으로밖에 움직일 수 없다. 왜냐하면 동, 동을 움직였다면 한 번만 방문해야 한다는 조건으로 인해서 다음에는 서쪽을 절대로 방문할 수 없다

 

따라서 O(N) = 4*3^(n-1)로 약 600만의 값으로 충분히 해결할 수 있는 시간이다

 

문제: https://www.acmicpc.net/problem/1405

https://www.acmicpc.net/problem/1405