https://www.acmicpc.net/problem/1726
최소를 구하는 것이므로, BFS 탐색을 활용한다.
네 방향의 델타 탐색에다가 방향 회전까지 더해진다.
방향을 함께 담기 위해 visited를 3차원으로 선언해 각 좌표의 방향마다 따로 처리해준다.
최소값을 계속 갱신해줘야 하니 나올 수 없는 최댓값으로 초기화한다.
방향을 90도 방향으로 할 수 있고, 전진은 1 ~ 3칸까지 가능하므로 5번의 경우를 확인한다. 방향은 우 하 좌 상으로 각각 1, 2, 3, 4로 입력이 들어온다. 따라서 0부터 시작하지 않으므로 padding을 visited를 선언할 때 넣어줘야 한다.
좌표는 padding을 넣기 귀찮으므로 넣지 않고 시작점과 도착점의 좌표값을 각각 1씩 뺀다.
방향이 우, 하인 경우는 좌, 상으로 회전시켜주면 된다. 그 때 더 최소값으로 visited를 바꿀 수 있으면 바꾸고 큐에 담는다.
전진은 1 ~ 3칸 할 수 있는데 입력받은 배열에 1이 있는지 확인한다. 1이 있으면 갈 수 없으므로 break로 다음 칸도 확인하지 않고 종료한다. 갈 수 있다면, 이동한 후 visited를 확인해 최소값인 경우 바꾸고 큐에 담아준다.
위 과정을 반복하며 원하는 도착점에 원하는 방향으로 도착했을 때 출력하고 종료한다.
from collections import deque
m, n = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(m)]
s_x, s_y, s_d = list(map(int, input().split())) # 시작점 좌표와 방향
e_x, e_y, e_d = list(map(int, input().split())) # 도착점 좌표와 방향
s_x -= 1 # 주어진 입력 좌표가 1,1부터 시작하는데 패딩을 넣기 귀찮으니 입력에서 각각 1을 빼준다.
s_y -= 1
e_x -= 1
e_y -= 1
INF = 100000
dx = [0, 0, 0, 1, -1] # padding + 우 좌 하 상
dy = [0, 1, -1, 0, 0]
visited = [[[0, INF, INF, INF, INF] for _ in range(n)] for _ in range(m)] # 네 방향 값으로 초기화 해준다.
visited[s_x][s_y][s_d] = 0 # 시작점은 명령이 0이니 넣어준다.
queue = deque()
queue.append((s_x, s_y, s_d)) # 시작점을 큐에 넣고 시작
while queue:
x, y, d = queue.popleft()
if [x, y, d] == [e_x, e_y, e_d]: # 도착점의 원하는 방향에 도달했을 때
print(visited[e_x][e_y][e_d]) # 명령받은 값을 출력하고 종료
break
for i in range(1, 5): # 방향 전환
if d in [1, 2] and i in [1, 2]: # d가 우, 좌 방향인데 회전할 방향도 우, 좌이면 안 된다.
continue
if d in [3, 4] and i in [3, 4]: # d가 하, 상 방향인데 회전할 방향도 하, 상이면 안 된다.
continue
if visited[x][y][i] > visited[x][y][d] + 1: # 회전했을 때 저장된 값보다 작으면 바꿔주고 큐에 담는다.
visited[x][y][i] = visited[x][y][d] + 1
queue.append((x, y, i))
for i in range(1, 4): # 전진, 1~3으로 움직일 수 있다.
nx = x + dx[d] * i
ny = y + dy[d] * i
if not (0 <= nx < m and 0 <= ny < n) or arr[nx][ny] == 1: # 중간에 갈 수 없으면 종료
break
if visited[nx][ny][d] > visited[x][y][d] + 1: # 전진했을 때 저장 값보다 작으면 바꿔주고 큐에 담는다.
visited[nx][ny][d] = visited[x][y][d] + 1
queue.append((nx, ny, d))