[백준/Python]15685: 드래곤 커브

문제

https://www.acmicpc.net/problem/15685
백준 문제집 - 0x0D강 - 시뮬레이션

 

알고리즘: 시뮬레이션

---

풀이

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

0세대 드래곤 커브는 길이가 1인 선분이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.
드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.
방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)

이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오.

 

🚨 이 문제는 각각의 행렬을 칸이 아닌 줄로 본다. 크기가 100x100 이지만 101개씩 생성해줘야한다.
(문제를 잘 보면 '격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.' 라고 되어있다.)
먼저 101x101 크기의 행렬과 드래곤 커브 좌표들을 저장할 set()을 생성한다.
set()으로 생성하는 이유는 드래곤 커브가 겹칠수도 있기 때문이다.

graph = [[0] * 101 for _ in range(101)]
curved = set()  # 드래곤 커브가 생성된 좌표

새로운 드래곤 커브는 기존 드래곤 커브의 끝점에서부터 시작된다.
끝점에서부터 기존 드래곤 커브를 90º 회전한 모습을 거꾸로 그려나가는셈이다.
즉, 0세대부터 N세대까지의 방향 변화값을 모두 저장해주면 된다.

 

우선 주어진 방향 정보에 맞게 방향값을 설정해준다.

directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]

차례대로 동, 북, 서, 남 방향이다.

 

x, y = 0, 0 이고 방향이 0인 드래곤 커브가 있다고 가정해보자.
(🚨 참고로 이 문제에서의 x, y는 행렬이 아닌 좌표기준으로 생각해야한다. x는 → 방향, y는 ↓ 방향으로 증가함.)

 

좌표는 (x, y), 행렬은 [y, x]로 표시하겠다.
0세대 드래곤 커브 = (0, 0) → (1, 0)

방향으로 따지면 동쪽 →
1세대 드래곤 커브를 만들기 위해선 끝점(1, 0)을 기준으로 90º 회전시켜야한다.

그리고 0세대 드래곤 커브의 끝부분부터 시작부분까지 거꾸로 그려나가야한다.
1세대 드래곤 커브 = (1, 0) → (1, -1)

방향으로 따지면 북쪽 ↑

 

잘 보면 문제에선 '시계방향'으로 90º 회전시켜야 한다고 했지만, 실제 방향은 동(→)에서 북(↑)으로 변화한것을 알 수 있다.
반시계 방향으로 90º 회전한것이다.
위에서 말했듯이 새로운 드래곤 커브는 기존 세대의 드래곤 커브의 끝부분부터 '거꾸로' 그려나가야한다.
다시 말해, [1, 0] → [0, 0] 를 90º 회전한 방향으로 그려야한다.
그럼 참고해야 할 방향은 동(→)이 아닌 서(←)가 되는것이다.
서(←)를 90º 뒤집으면 북(↑)이 되므로, 다음 방향을 계산할땐 현재 방향의 '반시계방향'으로 90º 회전한 값을 만들어 주면 된다.
즉, 기존의 방향값들을 뒤집은 후 해당 방향 인덱스값에서 +1 을 해주면 되는것이다.

 

입력값은 x, y, d, g 형태로 주어진다.
0부터 g세대까지의 방향을 저장하고, 해당 좌표를 set에 추가한다.

마지막으로 사각형의 갯수를 체크해야 한다.
기준 좌표가 (0, 0)일때 사각형의 나머지 좌표는 (0, 1), (1, 1), (1, 0)이 된다.
따라서 0번 행렬부터 99번 행렬까지 위 조건에 대입하고, 네개의 꼭지점 모두 set에 속한다면 카운트한다.

 

전체 코드

# 메모리: 31120KB / 시간: 44ms
from sys import stdin


input = stdin.readline

N = int(input())
# 100x100 격자이므로 행렬은 101개씩 생성
graph = [[0] * 101 for _ in range(101)]
directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]
curved = set()  # 드래곤 커브가 생성된 좌표


def curve(g, curr, path):
    if g == curr:
        return path
    # 다음 세대의 경로 = 기존 경로를 뒤집은 다음 90º씩 회전
    # 다음 세대의 시작점은 현재 세대의 끝점이기 때문에 뒤집어줘야함.
    new_path = [(p+1) % 4 for p in reversed(path)]
    return curve(g, curr+1, path + new_path)


def checking(y, x, path):
    for p in path:
        ny, nx = y + directions[p][0], x + directions[p][1]
        graph[ny][nx] = 1
        curved.add((ny, nx))
        y, x = ny, nx


for _ in range(N):
    x, y, d, g = map(int, input().split())
    # 0세대부터 g세대까지의 방향 변화를 저장
    path = curve(g, 0, [d])
    graph[y][x] = 1
    curved.add((y, x))
    checking(y, x, path)

ret = 0

for i in range(100):
    for j in range(100):
        if (i, j) in curved and (i+1, j) in curved and (i, j+1) in curved and (i+1, j+1) in curved:
            ret += 1

print(ret)

거북명령프로그램을 떠올리게 하는 문제다...