[TIL] 백준 13567 - 로봇 ( python )

📌 문제 탐색하기

M : 2차원 배열의 행, 열 값

matrix : M * M 2차원 배열

n: 명령어 개수

 

로봇은 (0, 0)에서 시작하며, 처음에 동쪽을 바라봅니다.
TURN 명령은 왼쪽(0)과 오른쪽(1)으로 90도 회전을 의미하며, 
MOVE 명령은 현재 바라보는 방향으로 d만큼 이동합니다.

명령어 실행 후 로봇이 matrix 내부나 경계에 있어야 명령어가 유효한지를 구하는 것이 핵심입니다.

 

1 ≤ M ≤ 1,000
1 ≤ n ≤ 1,000

가능한 시간복잡도

• M x M 크기의 배열을 생성하고, 모든 원소를 한 번씩 접근하므로 O(M^2)의 시간이 소요됩니다.
• n개의 명령어를 순차적으로 처리하며, 각 명령어마다 상수 시간 연산(O(1))을 수행하므로 전체적으로 O(n)의 시간이 소요됩니다.
• 전체 시간 복잡도:
  • 두 부분을 합하면 O(M² + n)이 됩니다.
  • 최악의 경우 약 1,000² + 1,000 = 약 1,001,000번의 연산이 발생합니다.
  • 1초에 1천만 번 정도 처리하기에 시간 내에 충분히 처리 가능한 수준입니다.

알고리즘 선택

로봇의 방향을 숫자로 관리하고 각 방향에 따라 x 또는 y 좌표가 증가하거나 감소하도록 구현해 보겠습니다.
예: 0 → 동, 1 → 북, 2 → 서, 3 → 남

---

📌 코드 설계하기

1. 문제의 Input을 받습니다.
2. 로봇의 초기 좌표 (y, x)를 (0, 0)으로 설정합니다.
3. 로봇의 초기 방향을 숫자 0(남쪽)으로 설정합니다.
4. 방향을 0, 1, 2, 3으로 표현하여 남, 서, 북, 동 순서로 정의합니다.
   1. 문제에는 0,0이 왼쪽 하단에 위치해있지만 쉽게 풀기 위하여 왼쪽 상단을 0,0이라고 생각했기에 방향을 이렇게 정했습니다.
5. TURN 명령 시,
   • TURN 0(왼쪽 회전)은 direction = (direction - 1) % 4
   • TURN 1(오른쪽 회전)은 direction = (direction + 1) % 4
6.  MOVE 명령 처리:
   1. 현재 방향에 따라 x, y 좌표를 다음과 같이 업데이트:
      • 님쪽(0): y += value
      • 서쪽(1): x -= value
      • 북쪽(2): y -= value
      • 동쪽(3): x += value
   2. MOVE 명령 수행 후, 경계 검사 함수를 통해 (y, x)가 유효한지 확인합니다.
   3. 만약 경계를 벗어난다면, 즉시 전체 명령어열을 무효 처리하고 종료합니다.
7. 모든 명령어가 유효하게 처리되었다면, 최종 좌표 (y, x)를 출력합니다.
8. 하나라도 유효하지 않은 명령어가 있었다면 -1을 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

M, n = map(int, input().split())
matrix = [[0] * M for _ in range(M)]

dir = 0
y, x = 0, 0
valid = True

for _ in range(n):
    command, value = input().split()
    value = int(value)
    
    if command == 'TURN':
        if value == 0:
            dir = (dir - 1) % 4
        else:
            dir = (dir + 1) % 4
    else:
        if dir == 0:
            y += value
        elif dir == 1:
            x -= value
        elif dir == 2:
            y -= value
        else:
            x += value

    if not (0 <= y < M and 0 <= x < M):
        valid = False
        break

if valid:
    print(y, x)
else:
    print(-1)