[프로그래머스] 60063 - 블록 이동하기 (Python)

로고를 누르면 문제 페이지로 이동합니다.

---

 

문제 설명

N x N 크기의 지도에서 2 x 1 크기의 로봇을 가장 왼쪽 위에서 가장 오른쪽 아래로 이동하는 데 걸리는 최소 시간을 구하는 문제입니다.

로봇이 차지하는 두 칸 중 어느 한 칸이라도 목적 지점에 도착하면 됩니다.

아래 그림은 5 x 5 크기의 지도에서의 출발 위치와 도착 위치를 나타낸 것입니다.

 

로봇은 1초에 한 방향으로 한번 이동하거나, 90도로 한번 회전할 수 있으며, 로봇이 이동하려는 위치는 빈 칸이어야 합니다.

아래 그림처럼 로봇이 회전할 때는 축이 되는 칸으로부터 대각선 방향에 있는 칸도 빈 칸이어야 합니다.

 

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

 

풀이

아이디어

로봇이 회전 없이 움직일 수 있는 경우는 다음과 같습니다.

 

로봇이 회전하는 경우는 다음과 같습니다. 이 때 0으로 표시한 위치는 빈 칸이어야 합니다.

 

단순 이동은 일반 BFS 탐색과 같습니다.

큐에 기준이 되는 위치(두 칸 중 행이 더 작거나 열이 더 작은 위치, (r1, c1))와 로봇의 방향(d), 이동 시간(mv)을 넣고, 하나씩 탐색합니다.

 

회전의 경우에는 위에서 구한 총 8가지의 경우를 직접 고려해주었습니다.

빈 칸이어야 하는 위치들이 ((로봇이 가로일 때 위, 아래로 이동), (로봇이 세로일 때 왼쪽, 오른쪽으로 이동))한 위치 입니다.

이때 로봇의 원래 위치를 r1, c1, r2, c2 라 하고, 위나 아래, 왼쪽, 오른쪽으로 이동한 로봇의 위치를 nr1, nc1, nr2, nc2 라 하면, 새로운 로봇의 위치들은 다음과 같습니다.

 

• 로봇이 현재 가로(1) 이고, 아래쪽(0)으로 이동 가능한 경우
  
  • 새로운 로봇이 (r1, c1, 바뀐 방향)
  • 새로운 로봇이 (r2, c2, 바뀐 방향) 

• 로봇이 현재 세로(0) 이고, 오른쪽(1)으로 이동 가능한 경우
  
  • 새로운 로봇이 (r1, c1, 바뀐 방향)
  • 새로운 로봇이 (r2, c2, 바뀐 방향) 

• 로봇이 현재 가로(1) 이고, 위쪽(2)으로 이동 가능한 경우
  
  • 새로운 로봇이 (nr1, nc1, 바뀐 방향)
  • 새로운 로봇이 (nr2, nc2, 바뀐 방향)

• 로봇이 현재 세로(0) 이고, 아래쪽(3)으로 이동 가능한 경우
  
  • 새로운 로봇이 (nr1, nc1, 바뀐 방향)
  • 새로운 로봇이 (nr2, nc2, 바뀐 방향)

 

코드 (Python)

위 내용을 구현한 코드입니다.

 

결과 (Python)

결과 화면입니다.