문제

• https://www.acmicpc.net/problem/15685

아이디어

• http://godingmath.com/rotation90
  • 회전, (y, x) -> (-x, y)
• lst에 꼭지점을 추가한다.
• 원점에서 가장 먼 곳, 즉, 회전기준점을 뽑기 위해 lst[-1]로 끝 점을 뽑아 낸다.
• 꼭지점을 회전하면서 회전한 점을 누적해서 lst에 추가한다.
• 꼭지점 추가가 끝나면, 격자판 최대 크기인 100 * 100을 순회하며 정사각형을 찾아서 카운트한다.

코드

N = int(input())

def arrayRotate(lst, arr): # 배열 회전
    size = len(lst)
    std_y = lst[-1][0] # 기준점 (끝점) 저장
    std_x = lst[-1][1]

    for i in range(size-1, -1, -1):
        y, x = lst[i][0]-std_y, lst[i][1]-std_x # 회전 기준점을 원점으로 이동

        lst.append([x+std_y, -y+std_x]) # 회전하고 다시 기준점으로 이동
        arr[x+std_y][-y+std_x] = True

def squareFind(arr, firstY, firstX): # 정사각형 찾는 함수
    if arr[firstY][firstX] == True and arr[firstY][firstX+1] == True and arr[firstY+1][firstX] == True and arr[firstY+1][firstX+1]:
        return True

    return False

arr = [[False] * 201 for _ in range(201)]

for _ in range(N):
    x, y, d, g = map(int, input().split())
    lst = []

    arr[y][x] = True
    lst.append([y, x]) # 시작점 추가

    if d == 0:
        x = x + 1
    elif d == 1:
        y = y - 1
    elif d == 2:
        x = x - 1
    else:
        y = y + 1

    lst.append([y, x]) # 0세대 추가
    arr[y][x] = True

    for i in range(1, g+1):
        arrayRotate(lst, arr)

ANS = 0
# 정사각형 찾기
for i in range(100):
    for j in range(100):
        if arr[i][j] == True:
            ANS += squareFind(arr, i, j)

print(ANS)

리뷰

• arrayRotate 함수 내부를 보면 for loop를 역순으로 순회하는 것을 볼 수 있다.
• lst[-1]로 기준점을 뽑아내기 때문에 역순으로 하지 순회하지 않으면, 가장 먼 점이 가장 위에 쌓이는 것이 아니라 처음에 쌓이게 되어서 순서가 섞인다.
• 다른 사람들 코드를 참고해보면 네방향 탐색처럼 좌표를 누적해서 계산한다 (범위를 벗어나는지 체크하면서)
• 네방향 밖에 없어서 방향만 리스트에 append하면서 풀면 쉽게 풀 수 있다
• 이 문제는 개인적으로 예제에 문제 설명이 기존의 x, y와 반대로 되어있어서 굉장히 헷갈렸다.
• 기준을 통일시켜서 헷갈리지 않게 조심해야겠다.

GIT

• https://github.com/Kimjaeseop/acmicpc/blob/master/15685/15685.py