1️⃣ 서론
이 문제는 백준 드래곤 커브 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
드래곤 커브는 다음과 같은 세가지 속성이 있다.
- 시작점
- 시작 방향
- 세대
K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.
크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하는 문제이다. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.
3️⃣ 풀이
처음에 바로 일종의 패턴들이 반복되어 시뮬레이션 문제라고 생각하였다. K 세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시키는 방법을 어떻게 코드로 표현할지 생각하다가 생각을 하지 못해서 풀이를 참고하였다.
하지만 나는 단순히 회전을 어떻게 해야할지를 고민했는데 그게 아닌, 일종의 규칙을 찾는 문제였다. 그 규칙은 다음과 같다.
일단, 방향을 문제와 같이 다음의 숫자로 규정한다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)
처음 시작 방향을 임의로 0으로 규정해보자
그럼 각각의 세대는 다음과 같은 방향을 갖는다.
0세대 : 0
1세대 : 0 1
2세대 : 0 1 2 1
3세대 : 0 1 2 1 2 3 2 1
4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1
이 강조된 부분을 전의 세대와 비교하면 다음과 같은 규칙을 찾을 수 있었다.
이전 세대의 정보를 뒤집어 거기에 1을 더해주면 된다. 4면 다시 처음인 0으로 돌린다.
이를 코드로 표현하면 다음과 같다.
1
(move[-i - 1] + 1) % 4
이제 최종 코드를 살펴보자
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
input = sys.stdin.readline
n = int(input())
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
# 드래곤 커브들이 모일 배열 1이면 드래곤 커브의 일부
arr = [[0] * 101 for _ in range(101)]
for _ in range(n):
# x, y : 드래곤 커브 시작점, d : 시작 방향, g : 세대
x, y, d, g = map(int, input().split())
arr[x][y] = 1
move = [d]
# g 세대 만큼 반복
for _ in range(g):
tmp = []
for i in range(len(move)):
tmp.append((move[-i - 1] + 1) % 4)
move.extend(tmp)
# 드래곤 커브에 해당하는 좌표 arr에 추가
for i in move:
nx = x + dx[i]
ny = y + dy[i]
arr[nx][ny] = 1
x, y = nx, ny
# 모든 꼭짓점이 드래곤 커브의 일부인 정사각형 개수 구하기
ans = 0
for i in range(100):
for j in range(100):
if arr[i][j] and arr[i + 1][j] and arr[i][j + 1] and arr[i + 1][j + 1]:
ans += 1
print(ans)
5️⃣ 마치며
도형이나 패턴 관련 문제가 나왔을 때 규칙이 있는지도 생각을 해봐야할 것 같다. 단순히 시뮬레이션 문제를 코드로 구현하는 것만 생각해서 쉽게 접근을 하지 못한 것 같다.
마지막으로 파이썬 extend 문법이 있는데 배열을 다른 배열의 원소로 펼쳐서 넣을 때 매우 유용하다. extend 사용법
