백준 15685번 - 드래곤 커브 [Python]

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

15685번: 드래곤 커브

문제

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

1. 시작 점
2. 시작 방향
3. 세대

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만 유효한 좌표이다.

문제 유형 / 난이도

구현 / 골드 4

문제 풀이

크기가 100x100이고 주어진 커브의 갯수는 최대 20개 까지이므로 주어진 커브를 모두 완성한 후 전체 그래프에서 찾아도 시간은 널널할 것이다. 따라서 모든 커브를 만든 후 그래프에 표시해 꼭지점 4개가 모두 해당되는 사각형을 구하면 된다. 그렇다면 여기서 관건은 드래곤 커브를 어떻게 구현할 것인지 이다. 문제에서는 드래곤 커브는 끝점을 기준으로 시계 방향으로 회전한다고 한다. 바로 위의 예시로 보면 이전에 왔던 방향 (0,-1)에서 (0,-2)로 왔던 방향을 시계방향으로 돌려서 이동한 좌표가 (-1,-2)이므로 지금까지 왔던 길을 역으로 다시 되돌아가면서 해당 방향의 시계방향으로 이동하면된다.

따라서, 커브를 만들 때 이동한 방향들을 stack에 저장해서 역으로 꺼내면서 시계방향으로 회전시키고 이동하면된다.

Python

import sys
input = sys.stdin.readline


def findSquare():
    global cnt
    for i in range(100):
        for j in range(100):
            if graph[i][j] and graph[i][j+1] and graph[i+1][j+1] and graph[i+1][j]:
                cnt += 1
                
def findCurve(x, y, d, g):
    stack = [d]
    graph[x][y] = 1
    x += dx[d]
    y += dy[d]
    graph[x][y] = 1
    for _ in range(1, g+1):
        temp = []
        for i in range(len(stack)-1, -1, -1):
            d = stack[i]
            d = (d+1)%4
            x += dx[d]
            y += dy[d]
            graph[x][y] = 1
            temp.append(d)
        stack += temp
    
n = int(input())

graph = [[0]*101 for _ in range(101)]

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

cnt = 0
for _ in range(n):
    x, y, d, g = map(int, input().split())
    findCurve(x, y, d, g)

findSquare()
print(cnt)

feedback

처음보는 유형이라 아이디어를 떠올리기 쉽지 않았다. 어떤 자료구조를 적용해야할까를 고민하다가 아이디어가 떠올랐다. 아이디어가 떠오르지 않을 때는 여러 자료 구조를 대입해보면서 풀 수 있는 방법을 물색하는 것도 좋은 솔루션인 것 같다.