드래곤 커브

문제를 풀지 못한 가장 큰 이유

1. 드래곤 커브가 생겨나는 것을 규칙성을 찾아 점화식으로 나타내고자 했지만, 규칙성을 찾아내지 못했다.

2. 예제 이해 못함 => 문제에서 주어진 좌표평면은 x축 : ➡ y축 : ⬇이다. 그렇기 때문에 시작 좌표가 (4,2)라면 ➡ 축으로 4칸, ⬇축으로 2칸인데 반대로 생각해서 이해하지 못했다.

3. 규칙성을 찾지 못한 탓인지 시작 좌표와 방향값만으로 g세대 드래곤 커브를 도출해내지 못했다.

규칙성 발견 과정

중요한 것은 좌표값 또는 좌표값 변화가 아니라, "방향값"과 "방향값 변화"다!!!⭐️⭐️⭐️⭐️⭐️ 방향값에 따라 다음 좌표를 계속해서 구할 수 있기 때문에, 시작점을 기준으로 방향값으로 다음좌표를 구해나가고, g세대 드래곤 커브도 구할 수 있다!

방향값은 바로 직전 세대의 드래곤 커브의 방향값에서 +1 되는 규칙을 발견할 수 있다! 즉, x세대 드래곤 커브의 방향값들을 리스트로 저장한다면, x+1 세대 드래곤 커브의 방향값들은 x세대의 방향값 요소들을 역순으로 조회하여 +1한 값을 순차적으로 저장하면 되는 것이다!

이 때, 방향값은 0,1,2,3 총 4개의 값이므로 4이상 되면 모듈러 연산을 통해 0,1,2,3으로 만들어주면 된다!

알고리즘

1. 시작점(x,y)와 방향 d로 다음 세대 드래곤 커브 구할 수 있다. 이전 세대의 방향값과 현재 세대 방향값 간의 규칙성을 찾을 수 있고, 이 규칙성으로 g세대 드래곤 커브도 구할 수 있다!

2. 드래곤 커브들의 꼭짓점 좌표를 마킹한다.(어떤 숫자든 상관없음. 일관성 있게 1로 통일한다.)

3. N개의 드래곤 커브 꼭짓점들 모두 마킹한 후 정사각형을 2차원 배열(=좌표평면) 상에 슬라이드 해나가며 정사각형의 4개 꼭짓점 좌표 모두 마킹되어 있으면 갯수 1씩 증가한다.

4. 카운팅한 정사각형 최종 갯수가 정답이 된다.

솔루션1 ① main함수 내에서 다음 방향값 & 다음 좌표 구하고 ② 정사각형 판단, 갯수 리턴하는 함수 구현

솔루션2 ① 다음 방향값 & 다음 좌표 구하는 함수 구현 ② 정사각형 판단, 갯수 리턴하는 함수 구현

솔루션 비교 : 함수를 따로 구현한 솔루션 2의 시간이 약 2배 정도 빨랐다! 하지만 구현해본 결과 참고한 소스코드가 혼란의 여지(전역변수 설정 및 초기화)가 있어서 그런지 더 헷갈렸다. 오히려 솔루션1이 시간은 좀 더 걸렸지만 직관적이고 코드도 더 간결했다.

다음에는 시간 보다는 직관적인 이해를 바탕으로 직관적인 코드로 먼저 작성하고, 시간 차이가 너무 많이(?) 날 경우, 리팩토링을 통해 시간을 줄이는 방법으로 하자!

솔루션2로 할거면 전역변수 설정할 때 초기화 관리 신경써야함