[Python] 백준 15685번 문제 풀이 - 드래곤 커브

문제 링크

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

문제 이해

이 문제는 각 세대의 드래곤 커브가 격자에 그려집니다.

이 때 1X1의 정사각형의 네 꼭짓점이 드래곤 커브의 일부인 정사각형 개수를 구하는 문제입니다.

 

드래곤 커브는 시작점, 방향, 세대로 그릴 수 있는데요

시작점은

y,x 좌표로 이루어져 있고

방향은

0 : → (x가 증가하는 방향)

1 : ↑ (y가 감소하는 방향)

2 : ← (x가 감소하는 방향)

3 : ↓ (y가 증가하는 방향)

세대가 좀 복잡한데

이렇게 끝점을 기준으로 90도 꺾어서 이전 세대의 커브를 붙이면 세대가 올라가는 형식입니다.

아이디어

처음에 세대가 3세대까지인줄 알고 

다음처럼 3세대까지 좌표를 구해서 격자에 True 표시해두고 정사각형의 4점이 전부 겹치는 곳을 찾을라고 했으나, 10세대까지 있는 것을 봤습니다. 그래서 규칙성을 찾으려 해봤지만 찾지 못해 다른 블로그를 참고 하였습니다.

다른 블로그에서는 좌표가 아닌 방향으로 규칙을 찾았었습니다.

https://velog.io/@ckstn0778/%EB%B0%B1%EC%A4%80-15685%EB%B2%88-%EB%93%9C%EB%9E%98%EA%B3%A4-%EC%BB%A4%EB%B8%8C-1-Python

 

이러한 규칙이 있었습니다.

이전 세대를 reverse하고 방향에 1씩 더해서 붙이면 다음세대가 된다.

예시를 들면 다음과 같습니다.

• 0세대 : 0
• 1세대 : 0 / 1(0+1)
• 2세대 : 0,1 / 2,1 (1+1, 0+1)
• 3세대 : 0,1,2,1 / 2,3,2,1(1+2, 2+1, 1+1, 0+1)

이렇게 세대별 드래곤커브를 구합니다.

 

그리고 정사각형이 가능한것은 0,0부터 오른쪽, 아래, 오른쪽아래대각선을 순차적으로 탐색하며 4꼭짓점이 모두 드래곤커브의 일부라면 결과값에 +1을 해줍니다.

 

정리하면 아이디어는 다음과 같습니다.

1. 시작점, 방향, 세대에 따른 드래곤 커브를 격자에 그린다.
   1. 그리는 방법은 이전세대를 reverse하고
   2. reverse한거를 +1하고 4로 나머지연산하여 배열에 저장한다.
   3. 그리고 배열을 돌며 드래곤 커브인 부분을 격자에 표시한다.
2. 0,0부터 시작하며 정사각형이 나오면 결과에 +1한다.

시간복잡도

아 아이디어의 시간복잡도는 드래곤커브의 개수는 20개이고 최대 세대는 10개입니다.

그렇다면 20 X 2^10 = 20480정도 격자를 돌며 드래곤커브가 거치는 구간에 선을 그어줍니다.

그리고 마지막 정사각형이 몇개인지 찾는 것은 X, Y 좌표를 돌며 하는건데 각각 최대값이 100이기 때문에 100 X 100 하면 10000이 됩니다.

그래서 20,000 + 10,000 → 30,000 으로 가능합니다.

코드 구현

import sys
input = sys.stdin.readline

n = int(input())

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

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

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

    curve = [d]
    graph[y][x] = 1

    for i in range(g):
        for j in range(len(curve)-1, -1, -1):
            curve.append((curve[j] + 1) % 4)

    for k in curve:
        y += dy[k]
        x += dx[k]

        if y < 0 or y > 100 or x < 0 or x > 100:
            continue

        graph[y][x] = 1

answer = 0

for i in range(100):
    for j in range(100):
        if graph[i][j] and graph[i+1][j] and graph[i][j+1] and graph[i+1][j+1]:
            answer += 1

print(answer)