[백준 1726] 로봇(Python)

1. 요약

바라보는 방향으로 궤도를 따라 움직이는 로봇이 있다. 움직이는 방향은 동, 서, 남, 북 중 하나이며, 다음 2가지의 명령을 통해 움직일 수 있다.

1. Go k: 현재 향하고 있는 방향으로 k칸 이동한다.
2. Turn dir: 현재 방향에서 오른쪽 또는 왼쪽으로 90도 회전한다.

공장 내 궤도가 설치되어 있는 상태가 2차원 행렬로 주어질 때, 도착지점과 도착지점에서 바라보는 방향을 바라보는데 필요한 최소 명령을 구해야한다. (단, 로봇은 궤도 설치 상태가 0인 곳만 움직 일 수 있다.)

2. 아이디어

BFS로 해결한다.

[y,x]칸에서 로봇이 바라보는 방향 to을 만드는데 필요한 최소 명령 횟수를 기록하는 3차원 배열(table)을 만든다.(평소에는 방문여부를 나타내는 변수 visited를 사용했지만 코드 라인을 줄이기 위해 table의 각 성분은 무한의 값으로 초기화)

주의

명령 1에서 바라보는 방향으로 2칸, 3칸으로 이동할 때, 궤도의 상태를 확인해야한다. 예를들어 로봇이 있는 칸 y, x에 있고바라보는 방향이 북쪽이고 3칸 이동 할 때 arr[y-1][x], arr[y-2][x], arr[y-3][x]는 모두 0의 값을 가져야한다.

3. 코드

import sys
from collections import deque

EAST, WEST, SOUTH, NORTH = 0, 1, 2, 3
r, c = map(int, sys.stdin.readline().rstrip().split())
arr = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(r)]

src_y, src_x, src_to = map(int, sys.stdin.readline().rstrip().split())
src_y -= 1
src_x -= 1
src_to -= 1

dst_y, dst_x, dst_to = map(int, sys.stdin.readline().rstrip().split())
dst_y -= 1
dst_x -= 1
dst_to -= 1
INF = int(1e9)

def isin(y, x):
    if -1<y<r:
        if -1<x<c: return True
    return False

def check(y, x, step, iter_count):
    for _ in range(iter_count):
        ny = y + step[0]
        nx = x + step[1]

        if not isin(ny, nx): return False
        if arr[ny][nx] == 1: return False

        y += step[0]
        x += step[1]

    return True

def solve():
    table = [[[INF for _ in range(c)] for _ in range(r)] for _ in range(4)]
    q = deque()
    q.append([0, src_y, src_x, src_to])
    table[src_to][src_y][src_x] = 0

    while q:
        cnt, y, x, to = q.popleft()

        # 명령 1. Go k 수행
        for i in range(1, 4):
            ok = True
            step = []

            if to == EAST:
                step = [0,1]
                ok = check(y, x, step, i)

            elif to == WEST:
                step = [0,-1]
                ok = check(y, x, step, i)

            elif to == SOUTH:
                step = [1,0]
                ok = check(y, x, step, i)

            else:
                step = [-1,0]
                ok = check(y, x, step, i)

            if not ok: break
            ny = y + step[0]*i
            nx = x + step[1]*i
         
            if arr[ny][nx] == 0:
                if table[to][ny][nx] > cnt + 1:
                    table[to][ny][nx] = cnt + 1
                    q.append([cnt+1, ny, nx, to])
        
        # 명령 2. Turn dir 수행
        if to == EAST or to == WEST:
            if table[SOUTH][y][x] > cnt + 1:
                table[SOUTH][y][x] = cnt + 1
                q.append([cnt+1, y, x, SOUTH])
            
            if table[NORTH][y][x] > cnt + 1:
                table[NORTH][y][x] = cnt + 1
                q.append([cnt+1, y, x, NORTH])
        
        if to == NORTH or to == SOUTH:
            if table[EAST][y][x] > cnt + 1:
                table[EAST][y][x] = cnt + 1
                q.append([cnt+1, y, x, EAST])
            
            if table[WEST][y][x] > cnt + 1:
                table[WEST][y][x] = cnt + 1
                q.append([cnt+1, y, x, WEST])
        
    print(table[dst_to][dst_y][dst_x])


solve()