많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.
-
명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
-
명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.
로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.
-
입력형식
-
첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다.
- 이때 M과 N은 둘 다 100이하의 자연수이다.
-
이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다.
-
다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.
-
마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다.
-
방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다.
-
출발지점에서 도착지점까지는 항상 이동이 가능하다.
-
-
-
출력형식
- 첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다
1. BFS를 이용한 풀이
from collections import deque
import sys
dx = [None, 0, 0, 1, -1]
dy = [None, 1, -1, 0, 0]
INF = 1e9
def direction_change_count(pre, post):
if pre == post:
return 0
elif (pre == 1 and post == 2) or (pre == 2 and post == 1):
return 2
elif (pre == 3 and post == 4) or (pre == 4 and post == 3):
return 2
else:
return 1
def bfs(start):
q = deque()
start_x, start_y, start_dir = start[0], start[1], start[2] # x, y, 방향
q.append((start_x, start_y, start_dir, 0)) # x, y, 방향, 명령 횟수
visited = set()
while q:
x, y, d, cnt = q.popleft()
if x == end[0] and y == end[1]:
return cnt + direction_change_count(d, end[2])
for i in range(1, 4):
nx, ny = x + dx[d] * i, y + dy[d] * i
if 0 <= nx < m and 0 <= ny < n and maps[nx][ny] == 0:
if (nx, ny, d, cnt + 1) not in visited:
q.append((nx, ny, d, cnt + 1))
visited.add((nx, ny, d, cnt + 1))
else:
break
for i in range(1, 5):
if i != d and (x, y, i, cnt + 1) not in visited:
q.append((x, y, i, cnt + direction_change_count(d, i)))
visited.add((x, y, i, cnt + direction_change_count(d, i)))
if __name__ == "__main__":
m, n = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
start = list(map(int, sys.stdin.readline().split())) # 출발 지점
end = list(map(int, sys.stdin.readline().split())) # 도착 지점
start[0], start[1] = start[0] - 1, start[1] - 1
end[0], end[1] = end[0] - 1, end[1] - 1
answer = bfs(start)
print(answer)
