A. 문제설명
https://www.acmicpc.net/problem/15685
문제에 대한 자세한 설명은 링크 참조
1. 시작점, 방향, 진행세대 수로 정의되는 드래곤 커브가 존재
2. 각 드래곤 커브는 시작점에서 시작해서 출발방향으로 이동하고, 세대의 진행에 따라 이전 세대의 드래곤 커브를 90도 회전시킨 후 끝점에 이어붙여서 확장
3. 주어진 세대로의 확장이 완료된 후 전체 좌표평면 내 드래곤커브가 걸쳐져 있는 사각형의 갯수 계수
이제 이걸 어떻게 그려야하나... 그림을 그려서 풀어야 할까?
B. 접근법
처음 이 문제를 받아보고 생각이 든 것은 드래곤 커브 자체의 그림에 대한 생각이었다. 그러나, 이 문제에서 집중해야 할 것은 그림 자체가 아니라 규칙성이다. 각 세대별로 이전 세대의 특징을 가지고 2배수의 크기로 확장하는 드래곤 커브는 이전 세대의 특성을 유지하고 그 것을 확장시킨다.
따라서, 이 문제의 인코딩 방식인 좌표평면내 선분말고 방향을 생각해보자.
방향의 정보를 0: →, 1: ↑, 2: ←, 3: ↓ 이라고 할 때 위 그림의 드래곤 커브의 정보는
1세대일 때: 0
2세대일 때: 0 1
3세대일 때: 0 1 2 1
4세대일 때: 0 1 2 1 2 3 2 1
를 가진다. 여기서 3세대와 4세대만 비교해 보자. 각 세대가 진행될 때 이전 세대의 커브를 90도 돌려 이어붙이는 것은 이전 세대의 커브인 [ 0 1 2 1 ]를 역순으로 돌려 [ 1 2 1 0 ]으로 만들고, 이에 대해 각 방향을 반시계로 돌려 1씩 증가시키는 것과 같다. 즉 [ 2 3 2 1 ]이 된다.
이는 모든 N세대의 커브와 N+1 세대의 커브를 비교했을 때 동일하게 나타나는 규칙성이고, 이를 이용하여 간단하게 드래곤 커브의 양상을 예측할 수 있다.
C. 풀이
1. 주어진 시작점과 방향정보를 기반으로 위 규칙성에 따라 나타날 드래곤 커브의 모든 방향정보를 구한다.
2. 해당 방향정보의 드래곤 커브를 가지고 실제 좌표에 그림을 그린다. 나의 경우, 좌표평면이 아닌 선분정보가 필요하므로 수평선과 수직선 2차원 배열을 이용하여 그렸다.
3. 마지막으로 드래곤 커브가 걸쳐져 있는 사각형의 갯수를 구해야 하는데, 좌표평면으로 수직선과 수평선이 걸쳐져 있는 좌표들을 모두 찍어주고, 좌표평면내 사각형의 갯수를 구한다.
* 여기서 나는 처음 3번에서 수직선과 수평선만으로 드래곤 커브가 걸쳐있는 사각형을 수직선과 수평선이 평행한 경우에 모두 구할 수 있다고 생각했다. 그러나 이 경우 아래와 같이 사각형의 우측하단 좌표에 꺾은 선이 걸쳐져 있는 케이스를 커버하지 못한다. 따라서 구현을 드래곤 커브가 지나는 모든 좌표를 찍는 방식으로 변경하였고, 케이스를 통과할 수 있었다.
D. 내 코드
