[백준 8911] 거북이 (Python)

문제 : 

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

8911번: 거북이

 

1. 문제 이해하기

• 좌표 위에 거북이가 움직인 지점을 모두 포함하는 가장 작은 직사각형의 넓이 구하기
• F : 한 눈금 앞으로, B : 한 눈금 뒤로, L: 왼쪽으로 90도 회전, R: 오른쪽으로 90도 회전
• 선분의 경우 넓이는 0
• 입력으로 테스트 케이스의 개수만큼의 테스트 케이스 결괏값을 출력하기

 

2. 문제 풀이 생각하기

1. 방향을 조정하는 L, R이 있기 때문에 방향과 현재 좌표를 저장해야겠다고 생각했습니다.
2. 방향은 북 : 0, 서 : 1, 남 : 2, 동 : 3
3. 가장 작은 직사각형의 가로, 세로를 구할 때 x축, y축 각각 가장 큰 값 - 가장 작은 값으로 구할 수 있다고 생각했습니다.
4. 그래서 행, 열을 각각의 set에 넣고 정렬 후 (가장 큰 행 값 - 가장 작은 행 값) * (가장 큰 열 값 - 가장 작은 열 값)으로 구했습니다.
5. 테스트 케이스마다의 결괏값을 ans 배열에 append 합니다.

 

파란색 점이 거북이가 이동한 지점이라고 가정하면

직사각형 넓이 = (x축에서 가장 큰 값 - x축에서 가장 작은 값) * (y축에서 가장 큰 값 - y축에서 가장 작은 값)

 

3. 차근차근 구현하기

import sys
input = sys.stdin.readline
n = int(input())
testCase = [list(input().strip()) for _ in range(n)]
d = [[-1,0], [0,-1], [1,0], [0, 1]] # 북 서 남 동
ans = []

for case in testCase:
    iArr = set()
    jArr = set()
    iArr.add(0) # 거북이가 지나간 y축 좌표 집합
    jArr.add(0) # 거북이가 지나간 x축 좌표 집합
    tutle = [0, 0, 0] # 방향, 행, 열
    for s in case:
        if s == "F":
            if tutle[0] == 0:
                tutle[1], tutle[2] = tutle[1] + d[0][0], tutle[2] + d[0][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 1:
                tutle[1], tutle[2] = tutle[1] + d[1][0], tutle[2] + d[1][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 2:
                tutle[1], tutle[2] = tutle[1] + d[2][0], tutle[2] + d[2][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 3:
                tutle[1], tutle[2] = tutle[1] + d[3][0], tutle[2] + d[3][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
        elif s == "B":
            if tutle[0] == 0:
                tutle[1], tutle[2] = tutle[1] - d[0][0], tutle[2] - d[0][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 1:
                tutle[1], tutle[2] = tutle[1] - d[1][0], tutle[2] - d[1][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 2:
                tutle[1], tutle[2] = tutle[1] - d[2][0], tutle[2] - d[2][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
            elif tutle[0] == 3:
                tutle[1], tutle[2] = tutle[1] - d[3][0], tutle[2] - d[3][1]
                iArr.add(tutle[1])
                jArr.add(tutle[2])
        elif s == "L":
            tutle[0] = (tutle[0] + 1) % 4
        elif s == "R":
            tutle[0] = (tutle[0] - 1) % 4
    sortI = sorted(iArr)
    sortJ = sorted(jArr)
    ans.append((sortI[-1] - sortI[0]) * (sortJ[-1] - sortJ[0]))
print("\n".join(map(str, ans)))

 

4. 피드백

• 처음에 방향을 상, 하, 좌, 우로 습관적으로 설정했었는데, 에러를 찾느라 생각보다 오래 걸렸습니다. 다음에는 이 점을 유의해서 풀이해야겠다고 생각했습니다.