미 정부 자료에 따르면, 교차로 사고의 53.1%가 좌회전 시 발생하며,

이와 반대로 우회전 시에는 5.7%만 발생한다.

미국 대도시에서 귀빈 고객만을 모시는 모범 택시 기사인 정원이는 고객의 안전을 위하여 승객을 태운 경우는 아예 우회전만 하기로 했다.

정원이의 도시는 2차원 지도로 나타나 있다. 정원이는 ‘A’에서 승객을 태우고 ‘B’까지 가려고 한다.

‘R’으로 표시된 곳이 도로이며, ‘X’로는 갈 수 없다.

정원이의 택시는 위, 아래, 왼쪽, 그리고 오른쪽으로만 움직이며 대각선으로는 갈 수 없고 지도 밖으로도 갈 수 없다.

시작 지점에서, 정원이는 인접한 곳에 도로만 있다면 상하좌우 어디든 갈 수 있지만,

그 다음부터는 진행하던 방향으로 직진하거나, 우회전만 할 수 있다.

정원이를 도와 A에서 B까지 직진과 우회전만으로 가는 최단경로의 길이를 구하는 프로그램을 작성하라.

우회전 timer 1s memory 64MB

우회전 1s 64MB