1726 - 로봇
📌 문제
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.
- 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
- 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.
공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.
로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.
📋 코드
from collections import deque
def direction(before, after):
if before == after:
return 0
elif (before, after) == (1, 2) or (before, after) == (2, 1) or (before, after) == (3, 4) or (before, after) == (4, 3):
return 2
else:
return 1
def bfs(i, j, dir, visited):
dx = [0, 0, 0, 1, -1]
dy = [0, 1, -1, 0, 0]
q = deque()
q.append((i, j, dir, 0))
visited[i][j][dir] = True
while q:
x, y, pos, count = q.popleft()
if x == ex-1 and y == ey-1:
return count + direction(pos, ed)
for i in range(1, 4):
nx, ny = x + dx[pos] * i, y + dy[pos] * i
if 0 <= nx < M and 0 <= ny < N and visited[nx][ny][pos]:
continue
if 0 <= nx < M and 0 <= ny < N and graph[nx][ny] != 1:
visited[nx][ny][pos] = True
q.append((nx, ny, pos, count + 1))
else:
break
for i in range(1, 5):
if not visited[x][y][i]:
visited[x][y][i] = True
q.append((x, y, i, count + direction(pos, i)))
M, N = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(M)]
visited = [[[False for _ in range(5)] for _ in range(N)] for _ in range(M)]
sx, sy, sd = map(int, input().split())
ex, ey, ed = map(int, input().split())
result = bfs(sx-1, sy-1, sd, visited)
print(result)💡 한마디
나중에 꼭 다시 풀어봐야겠다. 머리속에 그림은 쉽게 그려졌는데 구현하기가 너무 까다로웠다.
