[백준] #8911 거북이(python)

수영·2022년 10월 19일

Python3 백준

백준

목록 보기

75/117

📌문제

상근이는 2차원 평면 위에서 움직일 수 있는 거북이 로봇을 하나 가지고 있다. 거북이 로봇에게 내릴 수 있는 명령은 다음과 같이 네가지가 있다.

F: 한 눈금 앞으로
B: 한 눈금 뒤로
L: 왼쪽으로 90도 회전
R: 오른쪽으로 90도 회전

L과 R명령을 내렸을 때, 로봇은 이동하지 않고, 방향만 바꾼다. 명령을 나열한 것을 거북이 로봇의 컨트롤 프로그램이라고 한다.

상근이는 자신의 컨트롤 프로그램으로 거북이가 이동한 영역을 계산해보려고 한다. 거북이는 항상 x축과 y축에 평행한 방향으로만 이동한다. 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 직사각형의 모든 변은 x축이나 y축에 평행이어야 한다.

아래 그림에서 거북이는 가장 처음에 (0, 0)에 있고, 북쪽을 쳐다보고 있다. 컨트롤 프로그램이 FLFRFLBRBLB인 경우에 거북이는 아래와 같이 움직인다. 회색으로 빗금친 부분이 거북이가 지나간 영역을 모두 포함할 수 있는 가장 작은 직사각형이다. 넓이는 4가 된다.

거북이가 지나간 영역이 직사각형을 만들지 않는 경우도 있다. 예를 들어, FFLLFF인 경우에 거북이는 y축의 위로만 지나다닌다. 이 경우에 거북이가 지나간 영역을 모두 포함하는 직사각형은 선분이고, 선분은 한 변이 0인 직사각형으로 생각할 수 있다. 따라서, 선분의 경우에 넓이는 0이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 있고, 길이는 500을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이를 출력한다.

예제 입력1

3
FFLF
FFRRFF
FFFBBBRFFFBBB

예제 출력1

2
0
9

백준 8911번 문제

💡Idea

명령어에 따라 거북이🐢를 잘 움직이게 하고, 거북이가 거치는 모든 좌표들을 잘 기억하여 해당 좌표들을 모두 포함할 수 있는 직사각형의 크기를 구하는 문제입니다.

저는 이 문제를 풀 때 아래와 같은 두 가지를 생각하며 해결하였습니다.

거북이가 지나간 영역을 어떻게 저장할 것인가?

개인적으로, 거북이가 거쳐간 좌표들을 어떻게 저장할지를 생각해보고 풀어야 하는 문제라고 생각했습니다!

처음에는 거북이가 지나간 좌표들을 이차원 배열로 표현할까 생각했었습니다.

하지만 거북이가 지나갈 수 있는 좌표들의 범위가 따로 주어지지 않았기 때문에 고정된 이차원 배열을 만들 수 없으므로, 집합에 좌표들을 저장하여 문제를 풀 수 있도록 하였습니다.

거북이가 지나간 좌표들을 모두 포함할 수 있는 직사각형의 크기를 어떻게 구할 것인가?

거북이가 거쳐간 좌표들이 저장되어 있다고 할 때, 모든 좌표들을 포함하는 직사각형의 크기는 가장 큰 좌표와 가장 작은 좌표의 차이를 이용하면 됩니다.

존재하는 x좌표들과 y좌표들 별로 가장 큰 좌표와 가장 좌표를 구하면 두 좌표들의 차이가 직사각형의 한 변의 길이가 되고, 구한 두 변을 곱해주면 됩니다.

$(max(x) - min(x)) \times (max(y) - min(y))$

💻코드

⏰ 시간 : 1248 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline

pos = [(1, 0), (0, 1), (-1, 0), (0, -1)]
T = int(input())
for _ in range(T):
    cmd_list = input()
    turtle_direction = turtle_x = turtle_y = 0
    x_set = set([0])
    y_set = set([0])

    for cmd in cmd_list:
        if cmd == 'F': # 각 좌표 별로 한 칸씩 앞으로 이동 
            turtle_x += pos[turtle_direction][0]
            turtle_y += pos[turtle_direction][1]
        elif cmd == 'B': # 각 좌표 별로 한 칸씩 뒤로 이동 
            turtle_x -= pos[turtle_direction][0]
            turtle_y -= pos[turtle_direction][1]
        elif cmd == 'L': turtle_direction = (turtle_direction - 1) % 4 #리스트 왼쪽으로 이동
        else: turtle_direction = (turtle_direction + 1) % 4 #리스트 오른쪽으로 이동
        x_set.add(turtle_x)
        y_set.add(turtle_y)
	# 거북이가 지나온 영역의 최소 크기 계산
    print((max(x_set) - min(x_set)) * (max(y_set) - min(y_set)))

📝코드 설명

변수

pos : 거북이의 방향 전환을 위한 리스트로, 거북이가 오른쪽으로 90도씩 방향을 전환할 때마다 리스트의 오른쪽으로, 왼쪽으로 90도씩 방향을 전환할 때마다 리스트의 왼쪽으로 이동합니다. 거북이가 이동할 때, 현재 pos의 값만큼 이동합니다.
turtle_direction : 현재 pos의 위치를 말합니다.
turtle_x, turtle_y : 현재 거북이의 x좌표와 y좌표를 말합니다.
x_set, y_set: 거북이가 지나온 모든 x좌표와 y좌표를 말합니다.