[백준 15685번] 드래곤 커브 - python

문제 링크

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

15685번: 드래곤 커브

 

풀이 

규칙을 찾아야하는 문제이다. 나는 규칙을 찾지 못해서 블로그를 참고했다. 다양한 방식으로 접근하려는 노력을 해야겠다. 

 

규칙은 다음과 같다. 예를 들어, 시작 방향이 0이라고 하자

0세대 : 0 

1세대 : 0 1 

2세대 : 0 1 2 1

3세대 : 0 1 2 1 2 3 2 1

4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1

...

즉, n세대의 이동 방향은 n-1세대 방향 + n-1세대 방향을 거꾸로 뒤집고 각 방향에 +1을 해준 것이다.

이 때, 4일 경우 다시 0으로 돌아간다.

 

또한, 여기서 주의할 점은 범위가 0 <= x <= 100 이라는 것이다. 즉, 총 101칸 

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

n = int(input())

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

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

    move = [d]
	
    # g세대까지 방향 구하기 
    for _ in range(g):
        tmp = []
		
        # 이전 세대 거꾸로 뒤집고 + 1
        for j in move[::-1]:
            tmp.append((j+1)%4)
        # 기존 방향에 덧붙임 
        move.extend(tmp)
	
    # 드래곤 커브 표시 
    for i in move:
        x += dx[i]
        y += dy[i]
        graph[x][y] = 1

ans = 0

# 사각형 구하기
for i in range(100):
    for j in range(100):
        if graph[i][j] == 0 :
            continue

        if graph[i+1][j] and graph[i][j+1] and graph[i+1][j+1] :
            ans += 1

print(ans)