✅드래곤 커브 (골드4)

문제 출처 : https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

 

#1. 개선할 점

- 문제 제대로 읽자.

주어진 x, y가 시작점이라고 나와있는데 혼자 g세대의 한 좌표인 줄 알았다..............

 

- 회전 나왔다고 쫄지말자.

회전같이 한번에 바로 알 수 없는 애들은 순서대로 직접 해보면서 규칙을 찾아보자.

 

- 행, 열 제대로 확인하자. 여기서는 x가 열이고, y가 행이다!

 

- 여기서 규칙은 현 세대의 방향 배열은

전 세대에서 나왔던 방향 배열 + 그 배열을 reverse시킨 각 원소를 1증가시키고 4로 나눈 나머지 배열이라는 것이다.

 

ex) 4 2 1 3

 

0세대 : [1]

1세대 : [1, 2]

2세대 : [1, 2, 3, 2]

3세대 : [1, 2, 3, 2, 3, 0, 3, 2]

 

#2. 설계 및 풀이

 

1. 시작 방향을 배열에 넣고 g만큼 해당 규칙을 반복해서 방향 배열을 만든다.

2. 시작점을 방문처리 한 후, 방향배열을 따라가면서 방문처리 한다.

3. (0, 0)~(99, 99)까지 순회하면서 (0, 0)(0, 1)(1, 0)(1, 1)이 다 1이면 ans 증가시킨다.

 

# 드래곤 커브
import sys
input= sys.stdin.readline

dir = [(1, 0), (0, -1), (-1, 0), (0, 1)]
visited = [[0] * 101 for _ in range(101)]

n = int(input())
for _ in range(n) :
    x, y, d, g = map(int, input().split()) # y가 행, x가 열

    # 방향 배열 만들기
    arr = [d]
    for c in range(g) :
        temp = list(reversed(arr))
        for i in range(len(temp)) :
            temp[i] = (temp[i]+1) % 4
        arr += temp

    # 시작점부터 방향대로 따라가면서 방문처리
    visited[y][x] = 1
    for a in arr :
        x, y = x + dir[a][0], y + dir[a][1]
        visited[y][x] = 1

# 정사각형 개수 세기
ans = 0
for i in range(100) :
    for j in range(100) :
        if visited[i][j] == 1 and visited[i+1][j] == 1 and visited[i][j+1] and visited[i+1][j+1] == 1 :
            ans += 1

print(ans)