[알고리즘 문제] 회전판과 로봇 (Python / 파이썬)

문제

가로 N칸, 세로 M칸으로 이루어진 격자판이 주어지고, 그 중 한 개의 칸에 로봇이 존재한다. 로봇은 동(E), 서(W), 남(S), 북(N) 4 방향으로 움직일 수 있다. 각 칸에는 로봇이 얻을 수 있는 점수가 적혀있거나 장애물이 존재한다. 점수는 자연수로 주어지며, 장애물은 -1로 주어진다. 로봇은 움직일 때 마다 자신이 위치해 있는 곳의 점수를 얻게 되고, 해당 칸의 값은 0으로 바뀌게 된다. 로봇의 초기 위치에는 장애물이 존재하지 않으며, 항상 초기 위치에 있는 점수를 얻으며 움직이기 시작한다.
성우는 총 L회 로봇을 움직일 수 있으며, 각 회마다 성우는 로봇이 이동할 방향과 크기를 정해줄 수 있다. 예를 들어, 한 회에 로봇을 서쪽으로 3칸 움직일 수 있다. 이렇게 로봇이 이동하는 동안 방문하는 칸에 있는 점수를 얻게 된다. 단, 이동 중에 장애물을 만나거나 격자판의 모서리에 닿게 되면 로봇이 그 즉시 이동을 멈추고 다음 명령을 수행한다.

이동 중 장애물을 만나거나 모서리 혹은 벽면에 닿은 경우 - 빨간 화살표

로봇을 움직이는 명령이 너무 단조롭다고 느낀 성우는, 로봇이 이동하는 크기를 조금 더 복잡하게 정해보고자 한다.
로봇이 움직이는 크기는 회전판을 돌림으로써 정해진다. 회전판은 K개의 칸으로 이루어져 있으며, 각 칸에는 자연수가 적혀있다. 성우는 각 회마다 판을 한 번 회전시키고, 회전 결과 한 개의 숫자가 선택된다. 이 숫자만큼 로봇이 이동하게 된다. 그리고 회전판은 최초인 경우에는 지정된 기준에 따르고, 여러번 돌린 경우에는 직전 회전 결과를 기준으로 회전판을 돌린다.

성우는 판을 시계방향 혹은 반시계방향으로 판을 회전시킬 수 있다. 또한, 성우는 힘조절을 완벽하게 하기 때문에 판을 회전시킬 때에는 정확히 특정 칸 수만큼만 회전시킬 수 있다. 예를 들어, 크기 5인 회전판이 있고, 이는 위의 그림과 같다고 하자. 이 상황에서 성우가 회전판을 시계방향으로 회전시키면서 정확히 7칸만큼만 움직였다고 하자. 그러면 화살표는 0 → 1 → 3 → 5 → 2 → 0 → 1 순서대로 숫자를 가리키므로, 회전판은 마지막으로 숫자 1을 가리킨다. 따라서 로봇이 이동하는 크기는 1이 된다.
성우는 회전판과 함께 최종적으로 다음과 같은 명령을 내린다. 이 명령은 (이동 방향, 회전 방향, 회전시키는 칸 수) 로 주어진다. 회전 방향의 경우, 1은 시계방향을 나타내고 2는 반시계방향을 나타낸다. 다음은 이 명령의 예를 나타낸다.
N 1 2 : 회전판을 시계 방향으로 회전하며 2칸만큼 움직이고, 가리키는 숫자만큼 로봇을 북쪽으로 이동시킨다.E 2 8 : 회전판을 시계 반대방향으로 회전하며 8칸만큼 움직이고, 가리키는 숫자만큼 로봇을 동쪽으로 이동시킨다.
예를 들어, 지도와 회전판의 초기 상태가 위의 그림과 같고, 로봇이 (2, 5)에 위치해있는 경우에 “N 1 3” 의 명령을 내렸다고 하자. 그러면 성우는 시계방향으로 판을 회전시키면서 정확히 3칸을 움직이게 되므로, 회전판은 0 → 1 → 3 의 순서대로 숫자를 가리키게 된다. 따라서 북쪽으로 3만큼 움직이므로, 로봇의 최종 위치는 (2, 2)가 된다.
성우가 로봇을 L회 움직일 때, 로봇이 얻는 총 점수와 로봇의 최종위치 (x’, y’)를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스 T (1 <= T <= 10)가 주어지고, 그 다음 줄에 도로의 가로의 크기 N과 세로의 크기 M, 그리고 로봇의 현재 위치 X, Y 가 빈칸을 사이에 두고 주어진다. (1 <= N, M, X, Y <= 500) 다음 M개의 줄에 대하여 판의 상태가 주어진다. 각 칸에는 점수 혹은 장애물이 있으며, 점수는 200이하의 자연수로 주어지고 장애물은 -1로 주어진다.
그 후 다음 줄에 회전판에 존재하는 칸의 개수 K(1 <= K <= 8) 가 주어지고, 다음 줄에 회전판의 값들이 K개의 1000이하 자연수로 주어진다. 숫자는 회전판의 시계방향으로 주어지며, 회전판은 초기에 가장 앞의 숫자를 가리키고 있다.
그 다음 줄에 성우가 로봇을 움직이는 횟수 L(1 <= L <= 500) 이 주어지고, 이어 L개의 줄에 걸쳐 로봇을 움직이는 명령이 주어진다. 각 명령은 이동할 방향, 회전 방향, 회전시키는 칸 수로 이루어져 있다. 회전 방향의 경우, 시계 방향은 1로 주어지며 반시계방향은 2로 주어진다. 회전시키는 칸 수의 경우 100 이하의 자연수이다.

출력

T개의 테스트 케이스 각각에 대하여 로봇의 최종 위치와 점수를 출력한다. 각 줄은 “#x”, 로봇이 얻은 점수, 그리고 로봇의 최종 위치(x’, y’)를 각각 공백을 두고 출력한다. 단, x는 1부터 시작하는 테스트 케이스의 번호를 나타낸다.

---

문제 풀이

회전판과 로봇 문제는 회전판을 돌렸을 때 나오는 칸 수만큼 

로봇의 방향이 주어졌을 때, 그 방향으로 이동하는 문제이다. 

로봇은 상하좌우로 움직일 수 있으며 이동할 때마다 칸에 쓰여진 점수를 얻는다. 

이때, 주의 할 점은 점수를 얻은 자리는 0이 된다는 것이다. 

만약 로봇이 범위를 벗어나거나 장애물을 만나면 움직임을 멈추고 

다음 명령을 실행한다. 

회전판은 시계 혹은 반시계 방향으로 돌릴 수 있다. 

 

이러한 점을 모두 고려하여 로봇의 이동을 구현해주었다. 

먼저 로봇의 이동 방향을 구해주었다. 상하좌우로 이동하는 방향변수를 

정의해주었는데, 방향변수의 인덱스에 맞게 direction 변수를 정해주었다. 

그리고 로봇이 몇칸 이동해야하는지 구하기 위해

회전판을 시계 혹은 반시계 방향으로 회전시켜주었다. 

회전판은 인덱스를 이용해 회전시켜주었다. 

만약 시계 방향으로 회전하면 인덱스가 하나씩 작아진다. 

반시계 방향으로 회전하면 인덱스가 하나씩 증가한다. 

만약 범위가 벗어났을 때는 인덱스를 적절히 조정해주었다. 

구한 인덱스에 해당하는 회전판의 값만큼 로봇을 이동시켜주었다. 

앞서 구한 방향으로 로봇을 한칸씩 이동시킨다. 

만약 다음 위치가 범위 내이고 장애물이 아니라면 점수를 더해주고 

더한 자리를 0으로 만들어주고 로봇을 그 위치로 이동시켜준다. 

 

이 과정을 모두 반복하면 로봇이 얻는 점수와 최종 위치를 구할 수 있다. 

---

My Code

# 로봇의 이동 방향을 구하는 함수 
def get_direction(a):
    if a == 'N': direction = 0   # 북
    elif a == 'E': direction = 1 # 동
    elif a == 'S': direction = 2 # 남
    else: direction = 3          # 서 
    return direction

# 몇 칸 이동할지 구하는 함수 
def get_move(dir, dist, m):
    if dir == 1: # 시계 방향으로 회전 
        for i in range(dist): # 회전 시킬 칸 수 만큼
            m -= 1  # 인덱스를 왼쪽으로 이동시킴
            if m == -1: m = len(data) - 1 # 범위를 벗어나면 재설정
    elif dir == 2: # 반시계 방향으로 회전
        for i in range(dist): # 회전 시킬 칸 수 만큼
            m += 1  # 인덱스를 오른쪽으로 이동시킴
            if m == len(data): m = 0  # 범위를 벗어나면 재설정
    return m

# 상하좌우로 이동할 방향변수
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for tc in range(int(input())):
    m, n, y, x = map(int,input().split()) # 판의 가로, 세로, 로봇의 현재 위치 

    # 판의 상태 
    array = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        arr = list(map(int,input().split()))
        for j in range(1, m + 1):
            array[i][j] = arr[j - 1]

    k = int(input()) # 회전판의 칸 개수
    data = list(map(int,input().split())) # 회전판의 값
    move = 0 # 회전판이 가리키는 초기 인덱스 

    score = array[x][y] # 로봇의 첫 위치 점수가 점수의 초기값
    array[x][y] = 0 # 첫 위치의 점수를 가졌으므로 0으로 만듬

    l = int(input()) # 로봇을 움직이는 명령 횟수
    for _ in range(l):
        a, b, c = input().split() # 로봇 이동방향, 회전판 회전 방향, 회전 칸 수 

        direction = get_direction(a) # 로봇이 이동할 방향을 구해줌
        move = get_move(int(b), int(c), move) # 로봇이 이동할 칸 수를 구해줌

        for i in range(data[move]): # 구한 인덱스에 해당하는 값만큼 이동
            nx = x + dx[direction] # 구한 방향으로 이동
            ny = y + dy[direction]
            # 다음 위치가 범위 내이고 장애물이 아니라면
            if 1 <= nx <= n and 1 <= ny <= m and array[nx][ny] != -1:
                score += array[nx][ny] # 다음 위치의 점수를 더해줌
                array[nx][ny] = 0      # 점수를 얻었으므로 0으로 만듬
                x, y = nx, ny          # 로봇을 이동시켜줌 

    print('#' + str(tc + 1), end = ' ')
    print(score, y, x)