[구현, 시뮬레이션] 백준 - 8911번: 거북이 (파이썬)

https://www.acmicpc.net/problem/8911

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

# 입력
3
FFLF
FFRRFF
FFFBBBRFFFBBB

# 출력
2
0
9

 

---

거북이의 움직임을 시뮬레이션해서 다녀간 좌표들을 모두 포함하는 직사각형의 최솟값을 구해야 한다.
결론부터 보자면, 이 직사각형의 최솟값은 x, y 좌표의 각각 최댓값에서 최솟값을 뺀 값을 곱하면 된다.

(max(x) - min(x)) * ((max(y) - min(y))

 
 

for con in control:
    x, y = 0, 0
    looking = 0
    positions = [(x, y)]
    dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    for cmd in control:
        if cmd == 'F':
            x += dir[looking][0]
            y += dir[looking][1]
        elif cmd == 'B':
            x -= dir[looking][0]
            y -= dir[looking][1]
        elif cmd == 'L':
            looking = (looking - 1) % 4
        elif cmd == 'R':
            looking = (looking + 1) % 4

        positions.append((x, y))

    area = cal_min_square(positions)

거북이의 처음 위치와 바라보는 방향을 설정하고 구현을 시작했다.
명령어를 하나씩 수행하면서 거북이를 이동시키고, 도달했던 좌표들을 positions 리스트에 모두 기록해서 직사각형 넓이의 최솟값을 계산했다.
 

1 - Try

def cal_min_square(position):
    min_x = min(pos[0] for pos in position)
    max_x = max(pos[0] for pos in position)
    min_y = min(pos[1] for pos in position)
    max_y = max(pos[1] for pos in position)

    return (max_x - min_x) * (max_y - min_y)

t = int(input())
control = [input().strip() for _ in range(t)]

for con in control:
    x, y = 0, 0
    looking = 0
    positions = [(x, y)]
    dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    for cmd in control:
        if cmd == 'F':
            x += dir[looking][0]
            y += dir[looking][1]
        elif cmd == 'B':
            x -= dir[looking][0]
            y -= dir[looking][1]
        elif cmd == 'L':
            looking = (looking - 1) % 4
        elif cmd == 'R':
            looking = (looking + 1) % 4
        positions.append((x, y))

    print(cal_min_square(positions))

 
직사각형을 계산하는 부분에서 모두 for문으로 min, max 값을 찾은 게 문제였던 것 같아 이 부분을 수정해 보았다.
 

2 - Try

import sys

input = sys.stdin.readline

def cal_min_square(min_x, max_x, min_y, max_y):
    return (max_x - min_x) * (max_y - min_y)

t = int(input())
control = [input().strip() for _ in range(t)]

for con in control:
    x, y = 0, 0
    looking = 0
    dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    min_x = max_x = x
    min_y = max_y = y

    for cmd in con:
        if cmd == 'F':
            x += dir[looking][0]
            y += dir[looking][1]
        elif cmd == 'B':
            x -= dir[looking][0]
            y -= dir[looking][1]
        elif cmd == 'L':
            looking = (looking - 1) % 4
        elif cmd == 'R':
            looking = (looking + 1) % 4

        min_x = min(min_x, x)
        max_x = max(max_x, x)
        min_y = min(min_y, y)
        max_y = max(max_y, y)

    print(cal_min_square(min_x, max_x, min_y, max_y))

함수 밖의 for문에서 min, max 값을 갱신하면서 찾고, 최종 값으로 직사각형의 넓이를 구하는 방식으로 변경했다.
통과는 됐으나.. 다른 사람들의 코드에 비해 너무 느려서 최적화를 더 진행했다.
 

3 - Try

import sys

input = sys.stdin.readline

def cal_min_square(min_x, max_x, min_y, max_y):
    return (max_x - min_x) * (max_y - min_y)

# 직사각형 넓이의 최솟값 = (max(x) - min(x)) * ((max(y) - min(y))
# 이동한 모든 좌표들을 기록하고 위 식대로 계산

t = int(input())
control = [input().strip() for _ in range(t)]

for con in control:
    x, y = 0, 0
    looking = 0  # 0: 북, 1: 동, 2: 남, 3: 서
    dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    min_x, max_x = 0, 0
    min_y, max_y = 0, 0

    for cmd in con:
        if cmd == 'F':
            x += dir[looking][0]
            y += dir[looking][1]
        elif cmd == 'B':
            x -= dir[looking][0]
            y -= dir[looking][1]
        elif cmd == 'L':
            looking = (looking - 1) % 4
        elif cmd == 'R':
            looking = (looking + 1) % 4

        if min_x > x:
            min_x = x
        if max_x < x:
            max_x = x
        if min_y > y:
            min_y = y
        if max_y < y:
            max_y = y

    print(cal_min_square(min_x, max_x, min_y, max_y))

이번에는 if문으로 min, max 값을 비교하고, 조건에 만족하는 값만 min, max 변수에 갱신하도록 하였더니 시간이 대폭 감소하였다.
급하게 코드 짠다고 시간복잡도 생각 안 하고 막 짜는 버릇 좀 고쳐야 겠다,,