[삼성SW역량][Python/BOJ] 백준 15685 드래곤커브(시뮬레이션)

 

 

 

하나씩 그려서 반복되는 규칙을 찾는다.

그 규칙은 바로 1을 더한 후 거꾸로 해서 붙이는 것이다. (이걸 어떻게 생각하누...)

 

 

 

 

 

 

그림을 그린 후 아래 설명을 따라 숫자를 적으면 규칙을 찾을 수 있다. 

<그림을 그릴 때 이어붙일 그림의 끝점을 원래 그림의 끝점에 붙이면 된다.>  (밑에 그려놓은 그림 참고)

 

 

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음,

그것을 끝 점에 붙인 것이다.

 

 

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

 

 

예를 들어 방향이 1일 때를 해보면

 

 

 

0세대 : 1 

1세대 : 1 2

2세대 : 1 2 3 2 

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

 

 

0세대의 1에 1을 더하여 2를 만들어 1세대를 만들어준다.

1세대의 12에 1을 더하면 23이다. 이것을 뒤집으면 32이고 이것을 원래의 12에 붙여주면 1232이다. 

 

 

 

 

dx,dy를 만들 때 평소처럼 

 

 

이걸 보고 아하! 우 상 좌 하 구나 이렇게 만들면 틀린다. 

이 문제는 x축이 오른쪽으로 증가하는 방향이고,

y축이 아래쪽으로 증가하는 방향이기 때문이다. 

 

 

 

그러므로 dx,dy의 0번째에는 x좌표가 증가하는 방향인 1,0을 

1번째에는 y좌표가 감소하는 방향인 0,-1을 넣어주면 된다. 

 

dx = [1,0,-1,0]

dy = [0,-1,0,1] 이다. 

 

그러니까 옆에 화살표는 신경쓰지말고 말만 신경써서 만들면 된다. 

0은 x가 증가하는 방향 , 1은 y가 감소하는 방향으로 !! 

 

 

 

주의할 점 : 

x와 y가 처음부터 0-index이다. 

 

 

 

---

 

 

코드 : 

dx = [1,0,-1,0] 
dy = [0,-1,0,1]

                 
if __name__=="__main__" :
    n = int(input())
    mp = [[0]*101 for _ in range(101)]
    for _ in range(n) :
        x,y,d,g = map(int,input().split())
        mp[x][y] = 1 
        move = [d] # 방향 
        for _ in range(g) : # 세대 
            temp = []
            for i in range(len(move)) :
                temp.append((move[-i-1]+1)%4) # 거꾸로 1을 더해서 
            move.extend(temp)
        # 현재 move에는 방향이 들어있음 
        for i in move :
            nx,ny = x + dx[i], y + dy[i]
            mp[nx][ny] = 1 # 드래곤 커브가 있음을 표시 
            x,y = nx,ny
    ans = 0
    for i in range(100) :
        for j in range(100) :
            if mp[i][j] :
                if mp[i+1][j] and mp[i][j+1] and mp[i+1][j+1] :
                    ans+=1 
    print( ans )

 

 

 

 

거꾸로 값을 붙일 때  밑의 코드와 같이 해도 된다. 

  for i in range(g) :
        tmp = []
        for j in dir[::-1] :
            tmp.append((j+1)%4)
        dir.extend(tmp)

 

 

---

 

 

 

%4를 해주는 것 잊지말기!!!

그리고 간곳 표시해줄 때도 mp[x][y] = 1 을 해주어야한다.

이것을 안하면 원래 자리는 표시가 안된다.

 

 

 

복습하면서 나온 코드 : 

dx = [1,0,-1,0]
dy = [0,-1,0,1]


def dragon(x,y,d,g) :
    tmp = [d]
    for i in range(g) :
        tmp_add = []
        for j in range(len(tmp)) :
            tmp_add.append((tmp[j]+1)%4)
        tmp_add.reverse()
        tmp = tmp + tmp_add
    mp[x][y] = 1 
    for d in tmp :
        nx,ny = x + dx[d], y + dy[d] 
        mp[nx][ny] = 1 
        x,y = nx,ny


def check() :
    global ans 
    for i in range(100) :
        for j in range(100) :
            if mp[i][j] and mp[i+1][j] and mp[i][j+1] and mp[i+1][j+1] :
                ans +=1 
    return ans 
       
if __name__=="__main__" :
    n = int(input())
    mp = [[0]*(101) for _ in range(101)]
    for i in range(n) :
        x,y,d,g = map(int,input().split())
        dragon(x,y,d,g)
    ans = 0
    print(check())

 

 

 

 

 

 

참고 블로그 : 

 

https://kyun2da.github.io/2021/04/06/dragonCurve/

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

 

 

복습 :

✅ 20220714

✅ 20220715

✅ 20220716

✅ 20220725

🐾 20220918