[백준] 15685번 드래곤 커브 파이썬

드래곤 커브 속성 : 1. 시작점 / 2. 시작 방향 / 3. 세대

0세대 드래콘 커브 : 1인 선분

1세대 드래곤 커브 : 90도

2세대 드래곤 커브 : ...

K세대 드래곤 커즈 : K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것

100x100인 격자 위에 드래곤 커브 N개 존재.

크기가 1x1인 정사각형의 네 꼭짓점이 모두 드레곤 커브의 일부인 정사각형의 개수를 구하자.

 

- 입력

1줄 : 드래곤 커브의 개수 N()

2~N줄 : 드래곤 커브의 정보(x&y : 드래곤 커브의 시작점 / d : 시작 방향 / g : 세대)

* 방향 : 0: x좌표가 증가하는 방향 (→) / 1: y좌표가 감소하는 방향 (↑) / 2: x좌표가 감소하는 방향 (←) / 3: y좌표가 증가하는 방향 (↓)

 

- 출력

크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수

 

고민) 어떻게 이전 세대를 통으로 옮겨서 끝에 붙일까..?

n = int(input())
dragon_curve = [list(map(int, input().split())) for _ in range(n)]

#오, 위, 왼, 아래
direction = [[1,0], [0,1], [-1,0], [0,-1]]

def draw(curve_lines):
  last = curve_lines[-1]
  for line in curve_lines:
    x1, y1 = map(int, line.split())
    x2, y2 = map(int, line.split())
    ??
  
curve_line = []
for curve in dragon_curve:
  x, y, d, g = map(int, curve.split())
  curve_line.append([x,y])
  
  for i in range(g):
    new_curve = curve_line[:]
    draw(new_curve)

 

15685번 드래곤 커브

해답) x와 y가 최대 100까지 가능하므로 0으로 초기화한 arr이중리스트를 만들어 둔다. 

새로운 커브가 0 또는 arr의 최대 크기를 벗어난다면 continue하지만 그 안에 들어있다면 커브를 그릴 수 있으므로 arr[x][y]에 1을 넣는다. 최종 출력이 arr에서 사방이 모두 커브로 막혀 있는 사각형의 개수를 구해야 하므로 arr[i]

[j] 시리즈값들이 모두 1이라면 answer에 1을 더한다. 커브를 그릴 때, "이전 세대의 방향 정보를 뒤집고 1을 더해주는데 4라면 다시 0으로 되돌려서 이전 세대 끝에 붙이면 새로운 세대가 된다."를 유념한다. 즉, (move[ -i - 1 ] + 1) % 4로 규칙을 정의할 수 있다. 

import sys

input = sys.stdin.readline

n = int(input())

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

# 드래곤 커브들이 모일 배열 1이면 드래곤 커브의 일부
arr = [[0] * 101 for _ in range(101)]

for _ in range(n):
    # x, y : 드래곤 커브 시작점, d : 시작 방향, g : 세대
    x, y, d, g = map(int, input().split())
    arr[x][y] = 1

    move = [d]
    # g 세대 만큼 반복
    for _ in range(g):
        tmp = []
        for i in range(len(move)):
            tmp.append((move[-i - 1] + 1) % 4)
        move.extend(tmp)

    # 드래곤 커브에 해당하는 좌표 arr에 추가
    for i in move:
        nx = x + dx[i]
        ny = y + dy[i]
        arr[nx][ny] = 1
        x, y = nx, ny

# 모든 꼭짓점이 드래곤 커브의 일부인 정사각형 개수 구하기
ans = 0
for i in range(100):
    for j in range(100):
        if arr[i][j] and arr[i + 1][j] and arr[i][j + 1] and arr[i + 1][j + 1]:
            ans += 1

print(ans)

 

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

15685번: 드래곤 커브

참고 : https://tmdrl5779.tistory.com/146

[백준] 15685번 (python 파이썬)