최근 북한에서는 대북방송을 듣고 남쪽으로 귀순하는 병사들이 생길 것을 우려하여 비무장지대에 대인지뢰를 매설하고 있다.

국방부에서는 지뢰를 제거하는 로봇을 투입하여 지뢰매설 정보가 입수되는 대로 로봇이 이동하여 지뢰를 제거하도록 하였다.

로봇 하나가 담당하는 크기는 가로와 세로가 각각 N개인 정사각형 형태로 되어 있어서

각각의 위치는 (1. 1)부터 (N, N)까지 좌표형태로 나타낼 수 있다.

그런데 어떤 위치에는 나무나 바위와 같은 장애물이 있어서 로봇이 이동할 수 없다.

로봇은 앞으로 전진하거나 한번에 90도를 회전할 수 있다.

앞으로 전진하는 것은 전혀 어려움이 없지만 회전하는 데에는 상당한 부담이 되기 때문에 가능한 회전을 적게 하는 것이 좋다.

지뢰의 매설위치가 확인되는 대로 로봇에게 제거를 지시하면 로봇은 지시받은 순서대로 지뢰의 위치로 이동하여 제거하여야 한다.

로봇이 모든 지뢰를 제거하는데 필요한 최소의 회전횟수를 출력하는 프로그램을 작성하라.

지뢰제거1 timer 1s memory 256MB

지뢰제거1 1s 256MB