[파이썬/Python] 백준 13567번: 로봇

숨·2024년 9월 17일

코테

알고리즘 문제 풀이

목록 보기

77/105

📌 문제 : 백준 13567번

📌 문제 탐색하기

M : 정사각형 S의 한 변의 길이 $(1 ≤ M ≤ 1,000)$
n : 수행할 명령어 개수 $(1 ≤ n ≤ 1,000)$

(0, 0) 위치에서 동쪽을 본 상태에서 N개의 명령에 따라 이동했을 때 로봇의 최종 위치를 출력하는 문제이다.

문제 풀이

🤖 명령어 정리

MOVE d : 향하는 방향으로 d만큼 이동

TURN 0 : 현재 위치에서 왼쪽으로 90도 회전

TURN 1 : 현재 위치에서 오른쪽으로 90도 회전

모든 명령은 명령 수행 후 S의 경계 또는 내부에 있어야만 유효❗️

움직임은 로봇이 바라보고 있는 방향의 영향을 받기 때문에 방향에 대한 정보를 따로 정의해준다.
→ 동북서남을 directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]으로 정의하고 인덱스로 접근한다.

명령어에 대해 방향 변경하기
- TURN 0 → 현재 방향 정보에 -1
- TURN 1 → 현재 방향 정보에 +1
그 값을 4로 나눈 나머지를 인덱스에 다시 넣어 방향을 변경해준다.

명령어를 저장한 리스트를 하나씩 접근하면서 방향에 맞게 이동해주면 된다.

일련의 명령어 열을 이루는 각 명령어가 모두 유효하다면, 이 명령어 열을 유효하다고 한다.라고 했으므로, 로봇이 이동 중에 M * M 크기의 영역 S를 나간다면 명령어열이 유효하지 않게 된다.
→ 이동 후 영역 내에 있는지 확인한다.

유효 ❌ → 명령어 수행 중지 후 -1 출력 → 플래그 변수를 따로 정의해 이용한다.
유효 ⭕️ → 명령어 수행 지속

가능한 시간복잡도

for문으로 명령어 접근 → $O(n)$

최종 시간복잡도
$O(n)$ 로 최악의 경우 $O(1000)$ 가 되는데, 이는 1초 내에 연산 가능하다.

알고리즘 선택

명령어 하나하나에 접근하면서 현재 위치 연산하기

📌 코드 설계하기

필요한 입력 받기
이동 방향 정의
방향 상태 저장할 변수 정의
현 위치 초기화
유효 확인 플래그 정의
명령어 수행
6-1. 방향 전환 명령어라면 방향 바꾸기
6-2. 이동 명령어라면 현재 방향으로 이동
결과 출력

📌 시도 회차 수정 사항

1회차

    location += directions[now_direction] * int(order[1])
                                            ^^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: 'O'

명령어 따라 위치를 갱신하는 코드에서 str형으로 저장된 값을 int로 바꾸는데 에러가 발생했다. int형으로 변경할 수 없음을 의미하는 에러이다.

# 명령어 입력
orders = [list(input().rstrip()) for _ in range(n)]

명령어를 입력받을 때 위와 같이 입력받는 바람에 명령어가 한글자씩 분리되어 들어가서 숫자 위치에 명령어의 중간 글씨가 들어가는 바람에 int형으로 변환할 수 없었던 것이었다.
split()로 입력받도록 변경했다.

2회차

location += directions[now_direction] * int(order[1])

이 식으로 바로 위치를 갱신하려고 했는데 값이 갱신되는 것이 아닌 append()가 되었다.
인덱스로 접근해 갱신하는 식으로 변경했다.

3회차

이동 방향을 계산이 잘못되었는지 예제 입력1에 대해 -1만 나왔다. 이동 방향을 바꾸는 코드가 잘못된 것 같다.

		# 왼쪽 90도 회전
        if order[1] == '0':
            now_direction = (now_direction - 1) % 4
        # 오른쪽 90도 회전
        else:
            now_direction = (now_direction + 1) % 4

알고 보니 왼쪽 회전 시엔 현재 방향 인덱스에 +1, 오른쪽 회전 시엔 현재 방향 인덱스에 -1을 해주어야 하는데 반대로 입력해서 잘못된 결과를 얻었다.

📌 정답 코드

import sys

input = sys.stdin.readline

# M, n 입력
M, n = map(int, input().split())

# 명령어 입력
orders = [input().split() for _ in range(n)]

# 방향 정의
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# 방향 상태 초기화 (동쪽)
now_direction = 0

# 위치 초기화
location = [0, 0]

# 유효 확인 플래그 정의
valid = True

# 명령어 수행
for order in orders:
    # 방향 전환 명령어라면
    if order[0] == 'TURN':
        # 왼쪽 90도 회전
        if order[1] == '0':
            now_direction = (now_direction + 1) % 4
        # 오른쪽 90도 회전
        else:
            now_direction = (now_direction - 1) % 4
    # 움직이는 명령어라면
    else:
        # 현재 방향으로 이동
        location[0] += directions[now_direction][0] * int(order[1])
        location[1] += directions[now_direction][1] * int(order[1])

        if location[0] < 0 or location[0] > M or location[1] < 0 or location[1] > M:
            # 유효하지 않음 표시
            valid = False
            break

# 결과 출력
if not valid:
    print(-1)
else:
    print(' '.join(map(str, location)))