93. 로봇

백준

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 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)

참고