[백준] 15685 드래곤 커브, python

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

15685번: 드래곤 커브

시뮬레이션 문제이다. 

드래곤 커브를 만들면서 구해지는 꼭짓점을 모두 찾으면 되는 문제인데 이게 조금 복잡했다.

드래곤 커브를 만들때 다음과 같은 순서로 꼭짓점을 구했다.

1. 0세대 드래곤 커브를 구하고 현재 위치를 드래곤 커브의 마지막 점으로 설정한다.

2. 현재까지의 드래곤 커브로 다음 세대를 구한다.

  1)  마지막 꼭짓점부터 역방향 순회하고, 드래곤 커브의 꼭짓점 차이(방향)를 구해서 다음 꼭짓점 방향을 찾는다.

  2) 현재 위치에 다음 꼭짓점 방향을 더해서 다음 꼭짓점을 찾는다.

  3) 역방향 순회가 끝날때까지 1)~2)를 반복한다.

 

# import sys; input = sys.stdin.readline
MAX = 100
d = [(1, 0), (0, -1), (-1, 0), (0, 1)]

def make_dragon_curve(args):
    r, c, di, g = args
    ret = set()
    vertex = [(r, c), (r + d[di][0], c + d[di][1])] # 0 gen
    ret.add(vertex[0]); ret.add(vertex[1])
    cur_pos = list(vertex[-1])
    for _ in range(g):
        # reverse traversal
        N = len(vertex)
        for i in range(N - 1, 0, -1):
            dr = vertex[i][0] - vertex[i - 1][0]
            dc = vertex[i][1] - vertex[i - 1][1]
            ndr = dc
            ndc = -dr
            cur_pos[0] += ndr
            cur_pos[1] += ndc
            vertex.append(tuple(cur_pos))
            ret.add(tuple(cur_pos))
    return ret

def main():
    # 0 input
    N = int(input())
    # 1 input and find vertex in dragon curve
    vertices = set()
    for _ in range(N): # union
        vertices |= make_dragon_curve(map(int, input().split()))
    # 2 output, check square value
    answer = 0
    for i in range(MAX):
        for j in range(MAX):
            if (i, j) in vertices \
                    and (i, j + 1) in vertices \
                    and (i + 1, j) in vertices \
                    and (i + 1, j + 1) in vertices:
                answer += 1
    print(answer)



if __name__ == '__main__':
    main()

 

set 자료형을 사용했는데 이차원 배열로 체크해도 된다. 이차원 배열이 더 빠를줄 알았는데 큰 차이는 없었다.

# import sys; input = sys.stdin.readline
MAX = 100
d = [(1, 0), (0, -1), (-1, 0), (0, 1)]

def make_dragon_curve(r, c, di, g):
    global vertices
    vertex = [(r, c), (r + d[di][0], c + d[di][1])] # 0 gen
    cur_pos = list(vertex[-1])
    vertices[r][c] = True; vertices[r + d[di][0]][c + d[di][1]] = True
    for _ in range(g):
        # reverse traversal
        N = len(vertex)
        for i in range(N - 1, 0, -1):
            dr = vertex[i][0] - vertex[i - 1][0]
            dc = vertex[i][1] - vertex[i - 1][1]
            ndr = dc
            ndc = -dr
            cur_pos[0] += ndr
            cur_pos[1] += ndc
            vertex.append(tuple(cur_pos))
        # add new vertex
        for i in range(N, len(vertex)):
            vertices[vertex[i][0]][vertex[i][1]] = True

def main():
    # 0 input
    global vertices
    N = int(input())
    vertices = [[False for _ in range(MAX + 1)] for _ in range(MAX + 1)]
    # 1 input and find vertex in dragon curve
    for _ in range(N):
        r, c, di, g = map(int, input().split())
        make_dragon_curve(r, c, di, g)
    # 2 output, check square value
    answer = 0
    for i in range(MAX):
        for j in range(MAX):
            if vertices[i][j]\
                    and vertices[i][j + 1]\
                    and vertices[i + 1][j]\
                    and vertices[i + 1][j + 1]:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()