[백준] 15685 드래곤 커브

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

끝점에서 시계 방향으로 90도를 회전하였을 때, 어느 한 점이 끝점을 기준으로 하여 좌표에 어떤 변화가 일어났는지 알아야 했습니다.

90도 회전시 좌표 값의 변화량만 알게 되면, 드래곤 커브의 세대별 좌표를 모두 알아낼 수 있습니다.

 

문제 예제 1번에서 첫 입력을 예를 들어 (3,3) 을 시작으로 하면, 시작 방향에 따라 끝점은 (4,3) 가 됩니다.

이때 시작점과 끝점을 비교하면, x좌표는 1이 증가하고 y좌표는 변화가 없습니다.

이때 끝점을 기준으로 회전하면 (3,3)의 좌표가 (4,2)로 이동됩니다.

끝점이였던 (4, 3)와 변화된 좌표 (4,2)를 비교하면 x는 변화가 없고, y는 1이 감소하게 됩니다.

이를 토대로 x좌표 증가량만큼 y좌표가 감소하게 되는 것을 알 수 있습니다.

 

위의 과정들을 확인해 아래의 결과를 얻을 수 있었습니다.

(변화의 기준을 어디에 초점을 두느냐에 따라 다를 수 있습니다. 중요한것은 변화에 따른 규칙을 알아내야 합니다.)

• x 증가 -> y 감소
• x 감소 -> y 증가
• y 증가 -> x 증가
• y 감소 -> x 감소

 

이러한 과정으로 드래곤 커브의 모든 좌표를 구하였고, 집합에 기록하였습니다.

마지막으로 집합에 있는 좌표들을 확인하여 구하고자하는 조건에 만족하는 정답의 개수를 찾았습니다.

2) 알고리즘

• 구현

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def dragon_curve(n, dragon):                            # 남은 세대, 이전의 드래곤 커브
    if not n:                                           # 세대가 모두 진행되었다면 드래곤 커브 반환
        return dragon

    standard = dragon[-1]                               # 끝점은 항상 리스트의 마지막 요소
    new_dragon = []                                     # 90도 회전한 다음 세대의 좌표들
    for idx in range(len(dragon)-2, -1, -1):            # 끝점을 제외한 드래곤 커브 반복
        x, y = dragon[idx]

        diff_x = standard[0] - x                        # 끝점과 비교하여 각 좌표간의 거리 구하기
        diff_y = standard[1] - y

                                                        # 90도 회전한 새로운 좌표는
        nx = standard[0] + diff_y                       # x 좌표는 y좌표의 증가/감소량 만큼 증가/감소
        ny = standard[1] + (diff_x * -1)                # y 좌표는 x좌표의 증가/감소량 만큼 감소/증가

        new_dragon.append((nx, ny))                     # 새로운 좌표 추가
    
    return dragon_curve(n-1, dragon + new_dragon)       # 재귀 호출

dx = [1, 0, -1, 0]                                          # 오른쪽, 위, 왼쪽, 아래
dy = [0, -1, 0, 1]                                          

N = int(sys.stdin.readline())                               # 커브의 개수
dragons = set()                                             # 드래곤 커브의 좌표들
answer = 0

for _ in range(N):
    x, y, d, g = map(int, sys.stdin.readline().split())     # 좌표, 시작 방향, 세대

    nx = x + dx[d]                                          # 시작 방향에 따른 끝점
    ny = y + dy[d]

    dragons.update(dragon_curve(g, [(x, y), (nx, ny)]))     # 세대만큼 드래곤 커브 진행 후
                                                            # 드래곤 커브 좌표에 추가

for x, y in dragons:                        # 드래곤 커브의 좌표들을 모두 반복하며 정답 개수 찾기
    for k in [(1, 0), (0, 1), (1, 1)]:      # 1x1 사각형의 꼭지점 탐색
        cx = x + k[0]
        cy = y + k[1]

        if (cx, cy) not in dragons:         # 없다면 다음 좌표 탐색을 위해 종료
            break
    else:                                   # 모두 있다면, 정답 추가
        answer += 1

print(answer)

---

🔗 문제 링크

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

15685번: 드래곤 커브

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다