BOJ/백준-8911-Python

문제

코드

# https://www.acmicpc.net/problem/8911
# boj, 8911: 거북이, Python3
def solve(test_case: str) -> int:
    x, y = 0, 0    # 거북이는 가장 처음에 (0, 0)에 있고 (각 x, y의 위치를 담은 변수)
    dx, dy = 0, 1  # 북쪽을 쳐다보고 있다.  (각 x, y의 방향을 담은 변수)
    max_x, min_x, max_y, min_y = 0, 0, 0, 0  # 각 거북이가 이동한 영역의 x, y 최대, 최소 값을 저장하는 변수

    for case in test_case:  # 입력받은 test_case를 for 반복문으로 순차 조회
        if case == 'F':  # F: 한 눈금 앞으로
            x += dx
            y += dy
        elif case == 'B':  # B: 한 눈금 뒤로
            x -= dx
            y -= dy
        elif case == 'L':  # L: 왼쪽으로 90도 회전
            dx, dy = - dy, dx
        elif case == 'R':  # R: 오른쪽으로 90도 회전
            dx, dy = dy, -dx

        # 거북이가 이동한 영역을 포함하는 가장 작은 직사각형을 이동할때마다 계산
        min_x = min(min_x, x)
        max_x = max(max_x, x)
        min_y = min(min_y, y)
        max_y = max(max_y, y)
    
    # 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이 반환
    return (max_x - min_x) * (max_y - min_y)

if __name__ == '__main__':
    t = int(input())  # 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

    for _ in range(t):
        test_case = str(input())  # 컨트롤 프로그램이 주어진다.

        print(solve(test_case))

결과

ChatGPT Code

T = int(input())

for _ in range(T):
    directions = input().rstrip()

    x, y = 0, 0  # 초기 위치는 (0, 0)
    min_x, max_x, min_y, max_y = 0, 0, 0, 0
    # 거북이가 이동한 영역을 포함하는 최소 직사각형을 구하기 위한 변수 초기화

    for d in directions:
        if d == 'F':
            y += 1
            max_y = max(max_y, y)
        elif d == 'B':
            y -= 1
            min_y = min(min_y, y)
        elif d == 'L':
            x -= 1
            min_x = min(min_x, x)
        else:
            x += 1
            max_x = max(max_x, x)

    # 거북이가 이동한 영역을 모두 포함하는 가장 작은 직사각형의 넓이 계산
    width = max_x - min_x
    height = max_y - min_y
    print(width * height)

ChatGPT 문제풀이

해결 방법: 시뮬레이션

주어진 컨트롤 프로그램을 이용하여 거북이의 이동 경로를 시뮬레이션하면서 거북이가 이동한 영역을 포함하는 가장 작은 직사각형을 구할 수 있다. 거북이가 이동한 영역을 포함하는 가장 작은 직사각형은 가장 남쪽에 위치한 좌표와 가장 북쪽에 위치한 좌표, 가장 서쪽에 위치한 좌표와 가장 동쪽에 위치한 좌표를 이용하여 구할 수 있다. 이때, 거북이가 이동한 영역을 저장하기 위한 좌표 변수와 거북이가 현재 바라보는 방향을 저장하는 변수가 필요하다.

시간 복잡도: O(n)

문제 출처 & 깃허브

BOJ 8911
Github