드래곤 커브 백준 15685번 구현

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

문제
드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

시작 점
시작 방향
세대
0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

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

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

… 뭐 구현이 제일 까다롭고 생각할것도 많고 그렇기는 한데 힙, 그래프나 다른 문제를 풀어보고 싶다. 이것만 하고 이제 백준삼성SW말고 다른 유형의 문제를 보러 가야 겠다.

입력조건부터 봅시다.

드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다.

# 0 : ->, 1 : ↑, 2 : <-, 3 : ↓
n = int(input())
graph = [[0] * 101 for _ in range(101)]
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for i in range(n) :
    y, x, d, g = map(int, input().split())
    graph[x][y] = 1

입력조건에 따라서 n개의 드래곤커브 그리고 드래곤커브를 그릴 지도를 초기화를 하고 차례대로 입력을 받읍시다.

그리고 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)

그리고 커브 리스트를 봅시다. 일단 d는 시작 방향이라고 했습니다. 그리고 g는 세대입니다.

아직은 세대가 하나만 입력이 들어 있습니다. 그러니 j는 한번만 작동할 것이고 첫번째 for문 k는 -1,-1,-1이 되기에 아무 동작도 하지 않고 넘어갑니다.

여기서 curve[k]의 값은 상하좌우의 방향 값인데 방향값에다가 1을 더해주는게 곧 90도 회전하는 것과 같습니다. 그리고 그 범위는 0~3까지이니 4의 나머지를 사용해서 전체 방향회전을 구성합니다.

# 드래곤 커브
    for j in range(len(curve)) :
        x += dx[curve[j]]
        y += dy[curve[j]]
        if not 0 <= x < 101 or not 0 <= y < 101 :
            continue
        graph[x][y] = 1

첫번째 드래곤 커브입니다. x,y초기화한 값에다가 이동망한 dx,dy를 넣어줍시다. 그러면 커브의 개수만큼 이동을 반복할 것입니다. 이때 당연히 x와 y는 그래프안에 있는지 확인을 하고 가능한 범위라면 그래프에다가 1을 넣어줍니다.

이것을 드래곤커브의 개수만큼 반복을 해주면 됩니다.

curve에다가 print를 찍으면 위 처럼 그때그때 이동하는 방향이 어떻게 찍히는지 알 수 있습니다.

result = 0
for i in range(100) :
    for j in range(100) :
        if graph[i][j] == 1 and graph[i+1][j] == 1 and graph[i][j+1] == 1 and graph[i+1][j+1] == 1 :
            result += 1

print(result)

이제 처음부터 끝까지 이중for문으로 맵 전체를 탐색을 합시다.

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

네 꼭짓점 정사각형이 동시에 1일때 result를 1추가를 하고 출력을 합니다.