백준 #15685 - [G4] 드래곤 커브 : 구현

(python3)

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

문제 조건을 잘 읽어봐야합니다. 드래곤 커브가 격자 밖으로 빠져나가지 않는다는 조건 하나로 문제가 간결해집니다. 그리고 네모 변이 다 그려진 칸의 개수가 아니라 4개 점이 모두 드래곤 커브에 포함되는게 조건이라 이 부분도 파악하고 있어야합니다. 헷갈릴만한 부분들인것 같습니다.

 

구현 디테일

다음 세대에 포함될 점들을 찾아내는게 메인 파트입니다.

저는 항상 배열의 마지막 점이 다음 세대 드래곤 커브를 만드는 기준점이 되도록 다음 세대 점을 계산할 때 뒤쪽 점부터 계산했습니다.

기준점을 기준으로 시계방향 90도 회전한 점의 좌표 계산식만 헷갈리지 않고 작성하면 될 것 같습니다.

끝!

 

코드

def solution(input) : 
    # 격자점 0~101
    # 입력과 상수들
    coor = [[0]*101 for _ in range(101)]
    N = int(input().strip())
    dcurves = []
    for _ in range(N) :
        dcurves.append(list(map(int,input().split())))
    D = [(1,0),(0,-1),(-1,0),(0,1)]

    # dc 점들이 들어가면 다음 세대들도 뒤에 붙여주는 함수
    def next_generation(dc_points) :
        cx,cy = dc_points[-1]
        ndc_points = []
        for x,y in dc_points[-2::-1] : # dc 점들 순서 유지를 위해서 마지막부터 거꾸로 추가해줘야함
            nx = cx-y+cy
            ny = cy+x-cx
            ndc_points.append((nx,ny))
        dc_points += ndc_points

    # dc 입력 정보가 들어가면 dc 전체 점들을 만들어주는 함수
    def make_dragoncurve(dc) :
        x,y,d,g = dc
        dx, dy = D[d]
        dc_points = [(x,y), (x+dx, y+dy)]
        for _ in range(g) :
            next_generation(dc_points)
        return dc_points
    
    # dc 전체 점들을 좌표에 찍어줌
    def dc_to_coor(dc_points, coor) :
        for x,y in dc_points :
            coor[x][y] = 1

    # 정사각형 세기
    def cnt_square(coor) :
        cnt = 0
        for x in range(1,101) :
            for y in range(1,101) :
                if coor[x][y] == 1 and coor[x-1][y]== 1 and coor[x][y-1] and coor[x-1][y-1] ==1 :
                    cnt += 1
        return cnt
    
    # main
    for dc in dcurves :
        dc_points = make_dragoncurve(dc)
        dc_to_coor(dc_points, coor)
    
    cnt = cnt_square(coor)

    print(cnt)

solution(input)