백준 1726 로봇

from collections import deque
import sys

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
input = sys.stdin.readline

m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]
sx, sy, sd = map(int, input().split())
ax, ay, ad = map(int, input().split())

q = deque()
check = [[[-1] * 4 for _ in range(n)] for _ in range(m)]
q.append((sx-1, sy-1, sd-1, 0))
check[sx-1][sy-1][sd-1] = 0
while q:
    x, y, d, o = q.popleft()
    if x == ax - 1 and y == ay - 1 and d == ad - 1:
        print(o)
        break
    for step in range(1, 4):
        nx, ny = x + (step * dx[d]), y + (step * dy[d])
        if nx < 0 or ny < 0 or nx >= m or ny >= n or g[nx][ny] == 1:
            break
        # 우선순위를 이동에 줌 (더 많은 칸을 이동할 수 있으니까)
        if check[nx][ny][d] == -1 or check[nx][ny][d] == o+1:
            q.append((nx, ny, d, o+1))
            check[nx][ny][d] = o + 1
        else:
            break
    for dir in range(4):
        if dir != d and check[x][y][dir] == -1:
            if (d == 0 and dir == 1) or (d == 1 and dir == 0) or (d == 3 and dir == 2) or (d == 2 and dir == 3):
                q.append((x, y, dir, o+2))
                check[x][y][dir] = o + 2
            else:
                q.append((x, y, dir, o+1))
                check[x][y][dir] = o + 1

명령 1, 2룰 넣어서 bfs 돌림.

// 방향 순서도 변경해줌
if check[x][y][(d-1)%4] == -1:
        q.append((x, y, (d-1)%4, o+1))
    if check[x][y][(d+1)%4] == -1:
        q.append((x, y, (d+1)%4, o+1))
--------------------------------------------------
if d == 0 or d == 1:
        q.append((x, y, 2, o+1))
        q.append((x, y, 3, o+1))
    else:
        q.append((x, y, 0, o+1))
        q.append((x, y, 1, o+1))

처음에 명령2를 이런식으로 구현해서 메모리 초과 남. 큐에 같은 값이 너무 많이 들어가고 계속 한자리에서 돌아가는 문제가 있음. check 배열을 3차원으로 해서 방향을 넣고, 180도 회전은 2번 돌아간다고 생각해줌

while q:
    x, y, d, o = q.popleft()
    if x == ax - 1 and y == ay - 1 and d == ad - 1:
        print(o)
        break
    for step in range(1, 4):
        nx, ny = x + (step * dx[d]), y + (step * dy[d])
        if nx < 0 or ny < 0 or nx >= m or ny >= n:
            break
        if check[nx][ny][d] == -1 and g[nx][ny] == 0:
            q.append((nx, ny, d, o+1))
            check[nx][ny][d] = 0
        else:
            break
    for dir in range(4):
        if dir != d and check[x][y][dir] == -1:
            check[x][y][dir] = 0
            if (d == 0 and dir == 1) or (d == 1 and dir == 0) or (d == 3 and dir == 2) or (d == 2 and dir == 3):
                q.append((x, y, dir, o+2))
            else:
                q.append((x, y, dir, o+1))

수정해서 이렇게 했는데 바로 틀렸습니다 나옴
4 2
0 0
0 0
1 0
0 0
1 1 3
4 1 3
이런 반례가 있고 (질문 게시판에서 주움) 저렇게 하면 만약 명령1과 명령2(180도 돈 경우)로 도착한 시간이 같을 경우 우선순위가 명령2에 있게 돼서 틀리는 경우가 있어서 맨 처음 코드에서 주석 부분을 수정해주었다.