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

문제 보기

이 문제는 구현, 시뮬레이션 문제이다.

 

구현 문제는 아이디어가 가장 중요하다고 생각한다. 드래곤 커브 문제도 아이디어가 중요했는데 처음에는 잘 보이지 않았다. 하지만 주어진 예제를 직접 그려보면 바로 규칙이 보인다.

 

아래 값은 주어진 예제를 직접 그려보면서 세대 별로 방향 값을 나타낸 것이다.

 

0세대: 0

1세대: 0, 1

2세대: 0, 1, 2, 1

3세대: 0, 1, 2, 1, 2, 3, 2, 1

4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1

 

진하게 표현된 값이 추가된 값인데 특별한 규칙이 있는 것을 발견할 수 있다. 바로 이전 세대 방향 정보를 리버스 순서로 가져와서 1을 더하고 추가하면 된다. 만약 +1 한 값이 4라면 0 값을 추가한다.

 

코드

# 우, 상, 좌, 하
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


if __name__ == "__main__":
    n = int(input())  # 드래곤 커브의 개수
    data = [list(map(int, input().split())) for _ in range(n)]
    connect = [[] for _ in range(n)]  # 각 드래곤 커브가 연결된 선분 저장

    for i in range(n):  # 드래곤 커브 이동
        x, y, d, g = data[i]
        connect[i].append(d)  # 방향 삽입
        for _ in range(g):  # 세대 수 만큼 반복
            reverse = list(reversed(connect[i]))
            for j in reverse:
                if j + 1 == 4:
                    connect[i].append(0)
                else:
                    connect[i].append(j + 1)

    arr = [[False] * 101 for _ in range(101)]  # 정사각형 지도 초기화
    # 드래곤 커브 이동 값 지도 반영
    for i in range(n):
        x, y, d, g = data[i]
        arr[y][x] = True
        for j in connect[i]:
            x, y = x + dx[j], y + dy[j]
            if 0 <= x <= 100 and 0 <= y <= 100:
                arr[y][x] = True

    # 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수 파악
    answer = 0
    for i in range(100):
        for j in range(100):
            if arr[i][j] and arr[i][j + 1] and arr[i + 1][j] and arr[i + 1][j + 1]:
                answer += 1

    print(answer)