[Python][백준] 15685번 드래곤 커브

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

공부 날짜 : 2022.09.12
정답 참조 여부 : x

시작좌표와 방향, 숫자가 주어졌을때 드래곤 커브라는 규칙에 맞춰서 커브를 생성하고 좌표내에서 4개의 모서리가 모두 드래곤 커브의 좌표인 정사각형의 개수를 구하는 문제이다.

---

알고리즘을 사용할 필요도 없이 그냥 주어진대로 구현해서 좌표에 입력해준뒤 조건을 만족하는 정사각형의 개수를 세어나가면 되는 문제였다.

커브를 생성, 최대좌표 저장 -> 최대좌표를 바탕으로 그래프 생성 -> 커브에 맞춰서 그래프값 변경 -> 조건충족하는 정사각형 개수세기

별로 어렵지 않았다. 코드를 작성하는 과정에서 연산이 중복되는 부분이 많아서 시간초과가 되지 않을까 했지만 그런거 없이 바로 '맞았습니다'가 나왔다.

소스코드

import sys
from copy import deepcopy

input = sys.stdin.readline

#입력받은 드래곤 커브를 만드는 함수
def make_dragoncurve(x,y,dir,num):
    global max_x, max_y
    
    max_x = max(x,x+dx[dir],max_x)
    max_y = max(y,y+dy[dir],max_y)
    curve = [[x,y],[x+dx[dir],y+dy[dir]]]
    
    for _ in range(num):
        #회전 기준이되는 점
        point = curve[-1]
        #리스트 크기변화에따라 index변화를 방지하기위한 임시변수
        temp = len(curve)
        for i in range(temp-2,-1,-1):
            nx = point[0] - (curve[i][1] - point[1])
            ny = point[1] + (curve[i][0] - point[0])
            max_x = max(nx,max_x)
            max_y = max(ny,max_y)
            
            curve.append([nx,ny])
            
    return curve         
            

n = int(input())

#문제에서 주어진 방향
#우,상,좌,하
dx = [1,0,-1,0]
dy = [0,-1,0,1]

#정사각형 여부를 판단하기위한 그래프의 최대 좌표
max_x = 0
max_y = 0

#데이터 입력받아서 완성된 드래곤 커브를 저장
dragoncurve = []
for _ in range(n):
    x,y,dir,num = map(int, input().split())
    a = make_dragoncurve(x,y,dir,num)
    dragoncurve.append(deepcopy(a))

#판단해야하는 정사각형의 최대 크기
graph = [[False]*(max_x+1) for _ in range(max_y+1)]

for i in range(n):
    for x,y in dragoncurve[i]:
        graph[y][x] = True
        
result = 0   
#정사각형의 개수 카운트
for i in range(max_y):
    for j in range(max_x):
        if graph[i][j] and graph[i+1][j] and graph[i][j+1] and graph[i+1][j+1]:
            result += 1
        
print(result)