드래곤 커브

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

15685번: 드래곤 커브

문제요약:

좌표와 방향, 드래곤커브의 세대가 n개 주어진다. 드래곤 커브란 0세대는 그냥 한칸 방향따라 전진한 것이고 n세대 부터는 그전까지 간 좌표들을 마지막 좌표 기준으로 90도 회전시킨 좌표들을 뜻한다. 모든 좌표를 이동후, 크기가 1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 구하시오.

 

소요시간:

50분

난이도 골드4

 

코딩:

import sys 
input = sys.stdin.readline

n = int(input())

dragon = []
arr = [[0]*101 for _ in range(101)]

for _ in range(n):
    dragon.append(list(map(int,input().split())))

dx = [1,0,-1,0]
dy = [0,-1,0,1]

for x,y,dir,gen in dragon:
    arr[y][x] = 1
    arr[y+dy[dir]][x+dx[dir]] = 1
    temp1 = [[y,x],[y+dy[dir],x+dx[dir]]]
    for _ in range(gen):
        temp2 =temp1[::-1]
        l_y,l_x = temp2[0]
        for y,x in temp2:
            y-=l_y
            x-=l_x
            #90도 회전
            x,y = -y,x
            x+=l_x
            y+=l_y
            if 0<=y<101 and 0<=x<101:
                temp1.append([y,x])
                arr[y][x] = 1
ans = 0
for i in range(100):
    for j in range(100):
        if arr[i][j] and arr[i][j+1] and arr[i+1][j] and arr[i+1][j+1]:
            ans +=1

print(ans)

구현 문제입니다. 문제의 포인트는 회전 이동이였는데, 특정 점을 다른점을 기준으로 90도를 회전시키는 것이었습니다. 

이때 저는 특정지점과 기준점을 기준점이 (0,0)이 되게 대칭이동을 하고, (0,0)을 기준으로 시계방향으로 90도 회전시키면 (x,y)점이 (-y,x)이 되고 다시 대칭이동시켜주어 돌려주었습니다.

또한 이전세대의 점들의 집합중에서(temp1) 가장 첫번째 점이 이동후 그다음 세대의 기준점이 되게 때문에 중간에 temp2의 순서를 반전시켰고, temp2를 따로 만든 이유는 하나의 temp에 갱신을 하게되면 for문에서 갱신하면서 다시 추가하기 때문에 세대간을 구분하기 위함이었습니다.