[정올 1006] 로봇

문제

많은 공장에서 로봇이 이용되고 있다.

우리 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 

로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 

 

*명령 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칸에 벽이 있을 때 종료하지 않으면 벽을 뛰어넘어 다음 2칸을 탐색한다.

- Turn을 할 때 왼쪽이나 오른쪽으로 한 번만 Turn하도록 하였다.

 

위의 부분을 수정하여 다음과 같이 설계하였다.

- 위치와 방향을 담을 3차원 리스트를 준비한다. 해당 리스트를 통해 방문표시와 거리 표시를 한다.

- BFS을 진행하고 현재 위치에서 1~3칸을 이동한다.

- 이후 현재 위치에서 회전을 한다.

 

처음에는 이동과 회전을 2중 for문으로 한 번에 처리를 해줬는데 현재 위치에서 이동하지않고 회전만 하는 것을 고려하지 못하였다. 문제에서 주어진 조건을 확실하게 캐치하는 것이 중요하다고 생각했다.

 

구현

- 다음 리스트는 현재 위치에서 한 번의 Turn을 통해 바라볼 수 있는 방향을 나타낸 것이다.

- 해당 리스트에 방향이 존재하지 않는다면 2번의 명령이 이뤄져야한다.

direction = [[0, 3, 2], [1, 2, 3], [2, 0, 1], [3, 1, 0]]

- 시작위치에서 BFS를 실행한다.

- 3차원 리스트인 dist에 방문표시와 현재 거리까지 왔을 때 몇 번의 명령을 했는지 기록한다.

- 반복문 내에서 현재 위치가 도착위치이고 같은 방향일 때 dist에 해당되는 값을 반환한다.

- 그렇지않다면 현재 위치에서 1칸 ~ 3칸 이동하고

- 중간에 벽이 있을 때 종료한다.

- 이동한 정보를 큐에 넣은 후에는 현재 위치에서 방향을 회전한다.

- d가 현재 방향과 같다면 넘어가고

- 다른 방향일 때는 1번의 명령으로 가능한 것과 2번의 명령으로 가능한 것을 구분하여 dist에 방문표시를 한다.

def bfs(y, x, d):
    q = deque()
    dist = [[[0 for _ in range(4)] for _ in range(M)] for _ in range(N)]
    dist[y][x][d] = 1
    q.append((y, x, d))

    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]

    while q:
        cy, cx, cd = q.popleft()

        if cy == ey-1 and cx == ex-1 and cd == ed-1:
            return dist[cy][cx][cd] - 1

        for k in range(1, 4):
            ny = cy + (dy[cd] * k)
            nx = cx + (dx[cd] * k)
            if check_range(ny, nx) and board[ny][nx] == 1:
                break
            if check_range(ny, nx) and board[ny][nx] == 0:
                if dist[ny][nx][cd] == 0:
                    dist[ny][nx][cd] = dist[cy][cx][cd] + 1
                    q.append((ny, nx, cd))
            else:
                break

        for d in range(4):
            if d == cd:
                continue
            if dist[cy][cx][d] == 0:
                if d in direction[cd]:
                    dist[cy][cx][d] = dist[cy][cx][cd] + 1
                else:
                    dist[cy][cx][d] = dist[cy][cx][cd] + 2
                q.append((cy, cx, d))

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < M)

def bfs(y, x, d):
    q = deque()
    dist = [[[0 for _ in range(4)] for _ in range(M)] for _ in range(N)]
    dist[y][x][d] = 1
    q.append((y, x, d))

    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]

    while q:
        cy, cx, cd = q.popleft()

        if cy == ey-1 and cx == ex-1 and cd == ed-1:
            return dist[cy][cx][cd] - 1

        for k in range(1, 4):
            ny = cy + (dy[cd] * k)
            nx = cx + (dx[cd] * k)
            if check_range(ny, nx) and board[ny][nx] == 1:
                break
            if check_range(ny, nx) and board[ny][nx] == 0:
                if dist[ny][nx][cd] == 0:
                    dist[ny][nx][cd] = dist[cy][cx][cd] + 1
                    q.append((ny, nx, cd))
            else:
                break

        for d in range(4):
            if d == cd:
                continue
            if dist[cy][cx][d] == 0:
                if d in direction[cd]:
                    dist[cy][cx][d] = dist[cy][cx][cd] + 1
                else:
                    dist[cy][cx][d] = dist[cy][cx][cd] + 2
                q.append((cy, cx, d))

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

sy, sx, sd = map(int, input().split())
ey, ex, ed = map(int, input().split())

direction = [[0, 3, 2], [1, 2, 3], [2, 0, 1], [3, 1, 0]] # G-L-R
answer = bfs(sy-1, sx-1, sd-1)

print(answer)