백준 드래곤 커브 [15685] 파이썬(Python) 코드 + 해설

백준 15685 드래곤 커브 문제

문제 설명

드래곤 커브는 시작 점, 시작 방향, 세대를 가진다. 0세대 드래곤 커브는 길이가 1인 선분이며, 이후 세대는 이전 세대의 드래곤 커브를 끝점을 기준으로 시계 방향으로 90도 회전한 후, 끝점에 붙여서 만든다.

주어진 여러 개의 드래곤 커브를 그린 후, 좌표 평면 위에서 네 꼭짓점이 모두 드래곤 커브의 일부인 1×1 크기의 정사각형의 개수를 구하는 문제이다.

입력

• 첫째 줄: 드래곤 커브의 개수 N (1≤N≤20)
• 다음 N개의 줄: 각 드래곤 커브의 정보 x,y,d,g
  • x,y: 드래곤 커브의 시작 점 (0≤x,y≤100)
  • d: 시작 방향 (0≤d≤3)
    • 0: 오른쪽 (→)
    • 1: 위쪽 (↑)
    • 2: 왼쪽 (←)
    • 3: 아래쪽 (↓)
  • g: 세대 (0≤g≤10)

출력

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

문제 접근

드래곤 커브 생성 방법

드래곤 커브는 다음과 같은 방법으로 생성된다:

1. 0세대: 시작 점에서 시작하여 시작 방향으로 한 칸 이동한 선분.
2. n세대 (n ≥ 1):
   • 이전 세대의 드래곤 커브의 방향 배열을 가져온다.
   • 방향 배열을 역순으로 뒤집는다.
   • 각 방향을 90도 회전시킨다 (시계 방향).
   • 회전된 방향들을 이전 세대의 끝점에 이어붙인다.

방향과 회전

• 방향은 다음과 같이 표현된다:
  • 0: 오른쪽 (→) (x 증가)
  • 1: 위쪽 (↑) (y 감소)
  • 2: 왼쪽 (←) (x 감소)
  • 3: 아래쪽 (↓) (y 증가)
• 시계 방향으로 90도 회전하면:
  • 새로운 방향 = (현재 방향 + 1) % 4

구현 방법

1. 각 드래곤 커브에 대해:
   • 시작 점과 시작 방향을 저장한다.
   • 0세대의 방향 배열을 생성한다.
   • 세대마다 위에서 설명한 방법으로 방향 배열을 갱신한다.
   • 방향 배열에 따라 드래곤 커브의 좌표를 저장한다.
2. 좌표 평면에 표시:
   • 드래곤 커브가 지나는 모든 좌표를 2차원 배열에 표시한다.
3. 정사각형 개수 세기:
   • 전체 좌표 평면을 탐색하면서, 현재 좌표를 왼쪽 위 꼭짓점으로 하는 1×1 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인지 확인한다.
   • 만족하면 개수를 증가시킨다.

구현 코드(Python)

import sys

# 좌표 평면의 크기 설정 (0 ≤ x, y ≤ 100)
MAX_SIZE = 101

# 방향 이동을 위한 dx, dy
dx = [1, 0, -1, 0]  # 오른쪽, 위쪽, 왼쪽, 아래쪽
dy = [0, -1, 0, 1]

# 좌표 평면 초기화
grid = [[0] * MAX_SIZE for _ in range(MAX_SIZE)]

# 드래곤 커브 개수 입력
N = int(sys.stdin.readline())

# 드래곤 커브 정보 입력 및 처리
for _ in range(N):
    x, y, d, g = map(int, sys.stdin.readline().split())

    # 드래곤 커브의 방향 배열 생성
    directions = [d]  # 0세대 방향

    # 세대만큼 방향 배열 갱신
    for _ in range(g):
        temp = []
        for direction in reversed(directions):
            temp.append((direction + 1) % 4)
        directions.extend(temp)

    # 드래곤 커브 좌표 표시
    grid[y][x] = 1  # 시작 점 표시
    for direction in directions:
        nx = x + dx[direction]
        ny = y + dy[direction]
        if 0 <= nx < MAX_SIZE and 0 <= ny < MAX_SIZE:
            grid[ny][nx] = 1  # 이동한 좌표 표시
            x, y = nx, ny  # 현재 좌표 업데이트

# 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형 개수 세기
count = 0
for y in range(MAX_SIZE - 1):
    for x in range(MAX_SIZE - 1):
        if grid[y][x] and grid[y][x + 1] and grid[y + 1][x] and grid[y + 1][x + 1]:
            count += 1

# 결과 출력
print(count)

 

코드 설명

1. 방향 설정 및 좌표 평면 초기화

• dx, dy 배열을 통해 방향에 따른 x, y 좌표의 변화를 설정한다.
• grid는 101×101 크기의 2차원 배열로, 드래곤 커브가 지나는 좌표를 표시한다.

2. 드래곤 커브 생성

• 각 드래곤 커브에 대해 입력받은 시작 점 (x, y), 시작 방향 d, 세대 g를 사용하여 방향 배열 directions를 생성한다.
• 0세대의 방향 배열은 [d]로 시작한다.
• 각 세대마다 다음을 수행한다:
  • 현재 방향 배열을 역순으로 순회하면서, 각 방향을 시계 방향으로 90도 회전시킨 후 directions에 추가한다.
  • 회전은 (direction + 1) % 4 이다.

3. 드래곤 커브의 좌표 표시

• 시작 점 (x, y)를 grid에 표시한다.
• 방향 배열 directions를 순회하면서 다음 좌표를 계산하고 grid에 표시한다.
• 좌표를 계산할 때마다 x, y를 업데이트하여 현재 위치를 추적한다.

4. 정사각형 개수 세기

• 전체 좌표 평면을 순회하면서, (x, y)를 왼쪽 위 꼭짓점으로 하는 1×1 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인지 확인한다.
• grid[y][x], grid[y][x + 1], grid[y + 1][x], grid[y + 1][x + 1]이 모두 1이면 개수를 증가시킨다.

 

결과

백준 15685 드래곤 커브 정답

 

도움이 되셨다면 공감과 댓글 부탁드립니다.