Python/구현 BOJ-15685 드래곤커브

Posted on | In

[Python/구현] BOJ-15685 드래곤커브

📌문제링크 풀이참고


*풀이참고 링크 들어가셔서 보시면 됩니다.


세대가 거듭 될수록 2^k 만큼 선이 추가된다.

선이 어떤 패턴으로 추가 되는 걸까? 그림을 그리면 바로 이해된다.

✔ 세대 수 만큼 반복문을 통해 커브리스트를 뽑고 matrix에 그린 후 1x1 정사각형이 몇개가 있는지 세주면 된다. 단, x,y범위가 0<=x,y<=100 이므로 101x101 matrix를 활욯하자.


0세대 : 0

1세대 : 0, 1

2세대 : 0, 1, 2, 1

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

-> n 세대 = (n-1 세대 +1) 순서 뒤집기

*0: x좌표가 증가하는 방향 (→)

1: y좌표가 감소하는 방향 (↑)

2: x좌표가 감소하는 방향 (←)

3: y좌표가 증가하는 방향 (↓)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
board=[[0]*101 for _ in range(101)]
dx = [1,0,-1,0]
dy = [0,-1,0,1]

N = int(input())
for i in range(N):
    x,y,d,g = map(int,input().split())
    board[x][y]=1
    curve = [d]
    # 커브리스트 생성
    for j in range(g) :
        for k in range(len(curve)-1,-1,-1):
            curve.append((curve[k]+1)%4)
    # board에 그리기
    for di in curve :
        nx=x+dx[di]; ny=y+dy[di]
        if 0<=nx<=100 and 0<=ny<=100 :
            board[nx][ny]=1
            x=nx; y=ny
# 1x1 정사각형 세기
ans=0
for x in range(100):
    for y in range(100):
        if board[x][y] == 1 and board[x+1][y] == 1 and board[x][y+1] == 1 and board[x+1][y+1] == 1:
            ans +=1
print(ans)


회고

좌표가 반대로 적혀있어서 헷갈렸다.