문제

• 
• 시간 제한: 6초
• 메모리 제한: 256MB

Problem Analysis

가능한 경우는 위와 같이 계속 늘어난다. 이 중에서, 최적의 경우를 찾아야 한다. 재귀로 쪼개서 풀면, 한쪽으로만 깊게 들어갈 수 있다. 대신, BFS를 이용하면, 같은 level의 것들을 모두 조사하고 다음 level로 넘어갈 수 있다.

Algorithm

• BFS 를 통해, 각 level을 순차적으로 조사한다.
• 0~9999의 방문 여부를 기록하여, LLLL 같이 원점으로 돌아오는 경우를 건너뛴다.

Data Structure

• BFS 를 위한 Queue
• visited[10000], 0 ~ 9999 를 기록함

결과

Other

visited가 없다고 하면, 시간 복잡도는 O( 4^L ) 이다. (L = 답의 level)

경우의 수가 exponential 하게 늘어나기 때문에, 메모리와 시간관리를 위해서, 한 줄 한 줄 세심히 짜야 한다.

얼핏보면 tree 같지만, cycle이 존재하기 때문에 tree는 아니고 graph이다.