[백준] 로봇

https://www.acmicpc.net/problem/1726

1726번: 로봇

1. 문제 이해

로봇을 움직일 때 명령어가 한번 수행됩니다. 1 ~ 3만큼 이동시킬 수 있는 Go K 명령어와 왼쪽, 오른쪽으로 90도 만큼 움직일 수 있는 Turn dir 명령어가 있습니다. 출발지점과 현재 바라보는 방향에서 출발하여 도착지점에서 주어진 방향으로 바라볼 수 있기 위해 필요한 최소 명령어를 출력하면 됩니다.

2. 문제 접근

첫번째 접근: BFS

3차원 dist 배열과 heap을 사용한 BFS를 떠올릴 수 있었습니다. 각각의 위치에서 바라보고 있는 방향에 따라 필요한 명령어의 개수가 다르기 때문에 3차원 배열을 사용하였고 거리가 아닌 명령어가 항상 최소가 되어야하기에 heap을 사용하였습니다. 

3. 풀이

import sys, heapq
#sys.stdin = open("input.txt", "r")

input = sys.stdin.readline
# m: 세로, n: 가로 길이
m, n = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(m)
]

startY, startX, startDir = tuple(map(int, input().split()))
startY -= 1
startX -= 1
startDir -= 1

endY, endX, endDir = tuple(map(int, input().split()))
endY -= 1
endX -= 1
endDir -= 1

# 동, 서, 남 북
dys = [0, 0, 1, -1]
dxs = [1, -1, 0, 0]

q = [(0, startY, startX, startDir)]

# dist[dir][y][x]: y,x에 dir 방향으로 오는데 필요한 최소 거리
dist = [
    [[10000000 for _ in range(n)]
     for __ in range(m)]
    for ___ in range(4)
]

dist[startDir][startY][startX] = 0


def turnRignt(dir):
    if dir == 0:
        return 2
    elif dir == 1:
        return 3
    elif dir == 2:
        return 1
    else:
        return 0

def turnLeft(dir):
    if dir == 0:
        return 3
    elif dir == 1:
        return 2
    elif dir == 2:
        return 0
    else:
        return 1

def inRange(y, x):
    return 0 <= y < m and 0 <= x < n

while q:
    cnt, y, x, dir = heapq.heappop(q)

    # print("y : ", y, " x: ", x, " dir: ", dir, " cnt: ", cnt)
    if y == endY and x == endX and dir == endDir:
        print(cnt)
        break

    if dist[dir][y][x] < cnt:
        continue

    # go K를 수행
    for k in range(1, 4):
        temp = 0

        isOutOfRange = False
        ny = y
        nx = x

        while temp < k:
            ny += dys[dir]
            nx += dxs[dir]

            # 격자범위를 넘어가거나 갈 수 없는 지역인 경우
            if not inRange(ny, nx) or board[ny][nx] == 1:
                isOutOfRange = True
                break

            temp += 1


        if not isOutOfRange and dist[dir][ny][nx] > cnt + 1:
            dist[dir][ny][nx] = cnt + 1
            heapq.heappush(q, (cnt + 1, ny, nx, dir))


    # turn right을 수행해본다.
    nextDir = turnRignt(dir)

    if dist[nextDir][y][x] > cnt + 1:
        dist[nextDir][y][x] = cnt + 1
        heapq.heappush(q, (cnt + 1, y, x, nextDir))

    # turn left를 수행해본다.
    nextDir = turnLeft(dir)
    if dist[nextDir][y][x] > cnt + 1:
        dist[nextDir][y][x] = cnt + 1
        heapq.heappush(q, (cnt + 1, y, x, nextDir))

4. 회고

이 문제에서 제가 놓쳤던 부분은 한번에 2, 3 거리만큼 이동할 수 있는데 그 사이에 벽이 있는 경우에는 이동할 수가 없습니다. 이를 체크하는 것을 놓쳐서 푸는데 시간이 걸렸습니다.