23.03.16 파이썬 코딩 퀴즈#197 블록 이동하기 (프로그래머스 스쿨)

이번 문제는 블록 이동하기 문제이다.

크기가 2 x 1 인 로봇을 움직여서 지도의 N,N (지도의 최우측하단) 까지 이동해야 하며, 중간중간 벽(1)으로 막혀있다.

로봇의 시작 위치는 (1,1)이고, 가로방향으로 놓여져 있다.

위 이미지를 참고해서 생각해야 한다.

위 그림과 같이 로봇이 회전이 가능하며, 축은 어느 방향이든 설정 가능하다. 하지만 회전반경에 벽이 있는 경우에는 회전할 수 없다. 이동은 상하좌우 한칸씩 이동하며 (1,1) 에서 오른쪽으로 한칸 움직였다면 로봇의 좌표는 (1,2) 이고 차지하는 공간은 (1,2)와 (1,3) 이다. 또한 로봇이 한칸 이동하거나, 90도로 회전하는데에는 정확히 1초가 소요된다.

이제 주어진 board 를 확인하여, 로봇이 (N,N)까지 도달하는데 걸리는 시간을 구해 반환하면 된다.

먼저 생각해야할 부분은 회전에 관한 부분이다.

제한사항에 의해 로봇은 항상 목적지에 도착 가능하기 때문에 회전하는 위치는 신경쓰지 않아도 될듯하다.

다만, 회전을 진행해야 할때에는 한가지 더 신경써야 한다. 바로 로봇의 바로 위 두칸이 여유가 있어야 한다는 이야기이다.

즉 R 기준 회전 좌표와, L 기준 회전좌표 모두가 필요하게 된다. 

로봇이 세로로 배치되어 있는 경우도 마찬가지다.

먼저 solution() 함수이다. index 에러를 사전에 방지하기 위해 1(벽)로 채워진 new_board를 만들고 시작하였다.

그리고 이 new_board 에 전달받은 board 값을 가운데에 배치하여 주면 된다.

이러면 외벽이 1 로 둘러진 new_board 에 전달받은 board 가 들어가게 된다.

그리고 visited 에는 미리 로봇의 시작 좌표를 넣어준다.

while의 종료 조건은 q.popleft()로 뽑아낸 l(왼쪽 또는 위쪽), l (오른쪽 또는 아래쪽) 중 어느 한곳이라도 종료지점에 도달하면 종료된다.

이제 반복문을 이용해 next_move()라는 함수에서 전달받은 결과물을 돌게 되는데,

next_move() 함수의 전체 코드는 위와 같다.

먼저 전달받은 좌표 l, r 을 기준으로 4방향의 값을 확인한다. 이때 로봇의 배치 방향과 상관없이 상하좌우 두칸이 비어있다면, 로봇은 회전없이 이동이 가능하다. 따라서 해당 이동 가능한 좌표를 move_list에 전달한다.

로봇이 가로 방향일 경우에는 로봇의 위/아래만 신경쓰면 된다. 그리고 l 기준으로 회전이 될때에는 r 값을 변화시킨 (l, 변화된 l) 이 로봇의 위치좌표가 되고, r 기준으로 회전이 될때에는 (r, 변화된 r 값)이 로봇의 위치 좌표가 된다. 

세로 방향도 같은 방법으로 계산한다.

 

다시 solution() 함수로 넘어와서 해당 move_list 를 반복문으로 돌아서 결과 값을 확인해주면 된다.

회전이라는 조건 하나에 굉장히 저조한 통과율은 보이는 문제이다.

 

나도 처음에는 최적의 위치에서 회전하는 위치를 구현하기 위해 몇시간을 허비했다.

하지만 문제 제한사항에 보면 반드시 로봇은 목적지에 도달 가능하기 때문에, 굳이 회전의 최적화 위치까지 필요가 없었고, 양쪽 축 기준으로 회전시킨 좌표 2개를 다 사용하면, 먼저 통과한 좌표가 visited 에 남게되기 때문에 굳이 신경쓸 필요가 없게 된다.