[15685] 드래곤 커브

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

15685번: 드래곤 커브

구현 문제다. 규칙에 대한 파악과 x축과 y축 반전, 격자 칸의 수 등 실수를 유발하기 위한 장치들이 많은 문제라고 생각한다. 드래곤 커브에 대해 파악하는 데에 시간이 오래 걸렸던 문제다. 이런 유형의 경우 시간 내로 풀이를 생각하는 게 중요하다고 생각된다.

 

풀이

드래곤 커브의 움직임에 대해 이해가 필요한데, 문제에 주어진 번호에 따른 방향을 보면 힌트를 얻을 수 있다. 다음 세대의 움직임은 이전 세대의 다음 인덱스의 방향으로 움직이게 된다. 단 이전 세대의 움직임의 역순으로 추가를 시켜야 한다. 정리된 표를 통해 보면 이해하기 쉽다.

세대	(시작점 기준) 방향	번호
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 3 2 1)

일반적인 2차원 배열을 통해 풀어내려면 x축과 y축을 반대로 생각하고 풀어야 한다. 이어서 해당 문제는 격자가 100칸 즉 배열로 생성하려면 가로세로 101칸의 배열을 생성해야 100칸의 격자가 만들어진다. 본인의 경우 생각 없이 가로 세로 100칸의 배열을 생성했다가 오답 판정을 받았다. 입력되는 드래곤 커브는 격자의 범위를 벗어나지 않는다는 조건이 있으니 범위 체크는 하지 않아도 된다. 드래곤 커브로 둘러싸인 격자를 세는 방법은 인접한 4칸을 확인하며 세면 된다.

 

정답 코드