[이코테 Ch13-22] 블록 이동하기 (BFS)

👩🏻‍💻문제설명

[이코테 Ch13-22] 블록 이동하기 (BFS)

✍️Idea Sketch

시간복잡도

O(NM)

board를 탐색하는 BFS의 시간복잡도는 O(NM)이다. board의 가로 길이 * 세로 길이이다. 이 문제에서 board의 한 변의 길이는 100 이하이므로, 시간복잡도는 100 * 100 이하이다.

 

 

 

알고리즘 : BFS

(1, 1)에 존재하는 로봇을 (N, N)으로 옮기는 최단 거리를 계산하는 문제이다.

 

 

 

문제요약

출발지 (1, 1)에 존재하는 로봇을 목적지 (N, N)으로 옮기는 최단 거리를 계산하라.

일반적인 BFS 문제와는 다르게, 출발지에서 로봇이 차지하고 있는 위치가 두 칸이다.

상하좌우 이동은 물론, 특정 조건에서 회전도 할 수 있다.

 

 

 

회전조건

1. 가로로 놓인 로봇이 아래로 회전하는 경우

아래쪽의 두 칸이 모두 0인 경우, 회전할 수 있다.

2. 가로로 놓인 로봇이 위로 회전하는 경우

위쪽의 두 칸이 모두 0인 경우, 회전할 수 있다.

3. 세로로 놓인 로봇이 오른쪽으로 회전하는 경우

오른쪽의 두 칸이 모두 0인 경우, 회전할 수 있다.

4. 세로로 놓인 로봇이 왼쪽으로 회전하는 경우

왼쪽의 두 칸이 모두 0인 경우, 회전할 수 있다.

✍️내 소스코드

전체 코드

http://colorscripter.com/s/vGs3zMn