누구나 이해할 수 있는 백준 드래곤 커브 풀이 파이썬

백준 드래콘 커브 풀이 파이썬

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

15685번: 드래곤 커브

 

 

 

풀이 아이디어

예를 들어 4 2 1 3 이라고 해보자

3세대 까지의 결과

 

 

(설명은 x, y를 바꿔서 한다. 기존의 그래프 탐색처럼! 헷갈리니까)

 

2세대 까지 하면 아래와 같이 된다.

 arr = [[2, 4], [1,4], [1,3]]  - 기존세대 1세대

 arr2 = [[2, 4], [1,4], [1,3], [2,3], [2,2]]  - 추가된 세대 2세대

 

이제 2세대의 값들이 추가되는 과정을 이해해보자. 

먼저 1세대는 주황색까지이고 arr = [[2, 4], [1,4], [1,3]] 이라고 하자. 이제 이것을 기준으로 어떻게 저 검은선 2세대를 만들 수 있을까? 

관찰해보면 2세대에서 제일 처음 등장한 [2,3]은 arr의 기준점인 끝점 [1,3]을 기준으로 [1,4]와 대응된다는 것을 알 수 있다.

마찬가지로 2세대의 두번째 좌표 [2,2]는 [1,3]보다 arr의 인덱스 한칸 전인 [1,4]를 기준으로 [2,4]와 대응된다는 것을 알 수 있다.

즉, 기존의 세대의 좌표를 역순으로 탐색하면서 상대적인 위치를 구할 수 있게 될 것이다. 대응된다는 것을 알았으니, 이제 실질적인 좌표는 어떻게 나오는지 탐색해보자.

 

첫번째 좌표 [2,3]은 어떻게 나오는지?

arr의 끝점[1,3]을 기준으로 [1,4]와 대응되므로 먼저 [1,3]과 [1,4]의 차이를 구해보면 (0, -1) 이다. 시계방향으로 90도 회전이므로 x, y 좌표를 뒤집어보자. (-1, 0)이다. 이를 그래프의 끝 좌표인 [1,3]에 더하면 [0,3]이다. 우리가 원하는 [2,3]이 나오지 않았다. 하지만 길이차이는 동일하니, 부호의 차이인 것같다. 다시 관찰해보자.

 

자세히 탐색해보면 [1,3] 과 [1,4]는  왼쪽 좌표에서 오른쪽 좌표(오른쪽 방향)를 뺴는 것이니 마이너스 부호가 나오겠지만, 똑같은 길이로 2세대 드래곤 커브의 첫번째 좌표를 만들기 위해서는 아래 방향으로 이동하는 것을 알 수 있다. 아래 방향이라면 x좌표를 더해주어야 한다. 즉 아까 얻었던 값인 (-1,0)의 부호를 바꿔 (1,0)을 그래프의 끝 좌표 [1,3]에 더해주면 [2,3]이 나오는 것을 알 수 있다. 2세대의 값을 arr2를 따로 배열로 설정하고 여기에 값들을 저장해주자.

arr2 = [[2,4], [1,4], [1,3], [2,3]]  ([2,3] 추가)

 

끝점 [2,3]

 

 

두번째 좌표 [2,2]는 어떻게 나오는지?

먼저 [2,3]이 들어왔으므로 2세대의 끝점은 [1,3]이 아닌 [2,3]이 된다. 

 

arr = [[2, 4], [1,4], [1,3]] 

arr2 = [[2,4], [1,4], [1,3], [2,3]] 

 

다시 arr로 돌아가서 arr = [[2, 4], [1,4], [1,3]] 에서 역행으로 탐색을 한다고 하였으니 이제 [1,4]를 기준으로  [2,4]를 탐색하면 된다. 

[1,4] - [2,4] = [-1,0]이다. 앞서 했던 방식처럼 (0,-1)로  x, y 부호를 반대로 바꿔주고 2세대의 끝점 [2,3]에 더해준다. [2,2] 가 나온다. 이는 우리가 예상했던 값과 정확히 일치한다.

탐색후

 

그런데 앞서는 x,y를 바꾼 후 부호를 바꾸었는데 왜 이번엔 바꾸지 않아도 될까? [1,4]를 기준으로 [2,4]의 탐색은 아래 방향 이므로 (0,-1) 마이너스 부호이다. arr2의 끝점 [2,3]을 기준으로 새로 생긴 [2,2]로의 방향 또한 마이너스 부호이다.(y축 한칸 -1) 따라서 부호를 바꾸지 않아도 된다. 이런식으로 각 방향에 따른 방법을 탐색해보면 1세대의 탐색 이후 y 좌표의 값 차이가 달라지는 경우에 한해서 부호를 바꿔줘야 됨을 알 수 있게 된다. 

 

이 탐색이 끝나면 이제 2세대는  기존 세대가 된다.

따라서 배열을 아래와 같이 초기화하고 arr2인 3세대를 같은 방식으로 탐색하게 된다.

arr = [[2,4], [1,4], [1,3], [2,3], [2,2]] 

arr2 = [[2,4], [1,4], [1,3], [2,3], [2,2]] 

 

위의 내용을 바탕으로 아래의 코드를 이해해보면 납득이 갈 것이다. 

 

정답 코드

# 드래곤 커브
import sys
from collections import deque
si = sys.stdin.readline

N = int(si())
dragon_curve = deque(list(map(int, si().split())) for _ in range(N))
graph = [[0 for _ in range(101)] for _ in range(101)]

while dragon_curve:
    y, x, d, g = dragon_curve.popleft() # 기존 그래프 탐색처럼하기 위해 x,y 반대로
    

    arr = [[x, y]]
    # 0 세대는 미리 초기화
    if d == 0:
        arr.append([x, y+1])
    elif d == 1:
        arr.append([x-1, y])
    elif d == 2:
        arr.append([x, y-1])
    else:
        arr.append([x+1, y])

    # 1세대 부터 탐색 시작
    for i in range(1, g+1):
        arr2 = []
        arr2.extend(arr) # arr2 초기화

        # arr을 역순으로 탐색 시작
        arr_x, arr_y = arr.pop() # arr의 기준점
        while arr:
            check_x, check_y = arr.pop() # 기준점의 직전을 탐색
            diff_x, diff_y = arr_x - check_x, arr_y - check_y
            
            if diff_y > 0 or diff_y < 0:
                diff_y = diff_y * (-1)
            elif diff_x > 0 or diff_x < 0:
                pass # 바뀌지 않음
            
            # 90도 회전이므로 x, y 좌표 바꾸기
            diff_x, diff_y = diff_y, diff_x
            new_x, new_y = arr2[-1][0] + diff_x, arr2[-1][1] + diff_y
            arr2.append([new_x, new_y])

            # arr의 기준점 바꿔주기
            arr_x, arr_y = check_x, check_y 
        # arr2가 이제 arr로 기준세대로 바뀐다.
        arr.extend(arr2) 

    # 하나의 dragon_curve 탐색 끝
    while arr:
        x, y = arr.pop()
        graph[x][y] = 1 # dragon_curve가 있는 위치를 1로 저장한다.

# 오른쪽, 아래, 대각선 오른쪽 아래
dir = [[0,1], [1,0], [1,1]]
answer = 0
# 사각형이고 이중 for문으로 탐색하는 것이므로 범위를 100까지만
for i in range(100):
    for j in range(100):
        if graph[i][j] == 1: # 1이라면 탐색해볼 가치가 있으므로
            cnt = 1 
            for idx in range(3):
                nx, ny = i + dir[idx][0], j + dir[idx][1]
                if graph[nx][ny] == 1:
                    cnt += 1
            # cnt == 4로 사각형을 만족하는 경우
            if cnt == 4:
                answer += 1 
print(answer)