120. [삼성기출16]Python 백준 15685 번 드래곤 커브 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 15685 번 드래곤 커브 입니다.

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

15685번: 드래곤 커브

 

먼저 백준 15685 번 드래곤 커브 정답 코드입니다. 설명은 아래에 있습니다.

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
board = [[False for _ in range(101)] for _ in range(101)]
N = int(input())

for n in range(N):
    x, y, d, g = map(int, input().split())
    curve = [d]
    for i in range(g):
        for j in range(len(curve) - 1, -1, -1):
            curve.append((curve[j] + 1) % 4)

    board[y][x] = True
    for d in curve:
        x = x + dx[d]
        y = y + dy[d]
        board[y][x] = True

ans = 0
for i in range(100):
    for j in range(100):
        if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
            ans += 1
print(ans)

 

문제 접근

끝 점을 기준으로 시계방향 90도 회전합니다.

방향, 순서가 달라집니다.

 

첫 번째로 방향입니다.

예를들어 왼쪽에서 오른쪽으로 향하는 선분 ( → ) 을 회전시키면 위로 향하는 선분이 됩니다.( ↑ )

마찬가지로 위로 향하는 선분은 왼쪽으로, 왼쪽은 아래로, 아래쪽은  오른쪽으로

즉 문제에서 정의한 숫자로 표현하면

0(오른쪽) -> 1(위쪽)

1(위쪽) -> 2(왼쪽)

2(왼쪽) -> 3(아래쪽)

3(아래쪽) -> 0(오른쪽)

선분의 마지막 점의 부분을 기준으로 회전시켜서 상상하면 이해가 잘 됩니다.

 

다음은 순서입니다. 끝 점을 기준으로 90도 돌리게 되면 맨 뒤의 선분부터 다시 시작하는 모양이 됩니다.

 

그렇다면 방향이 0 1 2 3 인 드래곤 커브의 다음 세대는

1. 방향회전 : 1 2 3 0(4) 가 되고,

2. 순서 뒤집기 : 0 3 2 1

3. 원래 커브에 더하기 : 0 1 2 3 0 3 2 1 이 됩니다.

방향대로 모든 좌표를 구해서 그래프에 표시 하면 됩니다.

 

 

Python 코드 구현

 

방향구현을 위한 리스트와 드래곤 커브를 그릴 2차원 리스트를 생성합니다.

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
board = [[False for _ in range(101)] for _ in range(101)]
N = int(input())

 

첫 번째 for문에서는 커브 개수만큼 반복하며 정보를 입력 받습니다.

두 번째 for 문에서는 입력받은 세대까지의 드래곤 커브를 생성합니다.

세 번째 for 문에서는 이전 세대의 드래곤 커브를 거꾸로 돌면서 1을 더하고 4를 나눈 나머지를 

새로운 커브에 추가합니다. 

for n in range(N):
    x, y, d, g = map(int, input().split())
    curve = [d]
    for i in range(g):
        for j in range(len(curve) - 1, -1, -1):
            curve.append((curve[j] + 1) % 4)

 

드래곤 커브 하나가 다 만들어 졌습니다.

아래의 코드를 통해 커브의 모든 좌표에 표시합니다. 

board[y][x] = True
for d in curve:
    x = x + dx[d]
    y = y + dy[d]
    board[y][x] = True

 

 그래프를 탐색하면서 1*1(선분) 크기의 정사각형의 개수를 세고 답을 출력합니다.

ans = 0
for i in range(100):
    for j in range(100):
        if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
            ans += 1
print(ans)

 

파이썬 백준 15685 번 드래곤 커브 최종 코드입니다. 

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
board = [[False for _ in range(101)] for _ in range(101)]
N = int(input())

for n in range(N):
    x, y, d, g = map(int, input().split())
    curve = [d]
    for i in range(g):
        for j in range(len(curve) - 1, -1, -1):
            curve.append((curve[j] + 1) % 4)

    board[y][x] = True
    for d in curve:
        x = x + dx[d]
        y = y + dy[d]
        board[y][x] = True

ans = 0
for i in range(100):
    for j in range(100):
        if board[i][j] and board[i + 1][j] and board[i][j + 1] and board[i + 1][j + 1]:
            ans += 1
print(ans)

 

백준 15685 번 드래곤 커브 자세한 설명 및 Python 코드였습니다.

감사합니다.