백준 - 15685번(드래곤 커브) / C++

문제링크 : https://www.acmicpc.net/problem/15685

15685번: 드래곤 커브

인풋이 주어질때 좌표평면의 x,y값으로 주어져서 굉장히 헷갈리는 문제였다.

코드를 짤때 애초에 r,c를 이용했으면 덜 헷갈렸을 문제이다.

 

문제풀이 : 

처음 좌표를 벡터에 담고 d값을 통해 두번째 좌표 또한 벡터에 담는다.

이 과정에서 벡터에는 0세대 드래곤 커브가 담겨있다.

 

이제 0세대 드래곤 커브를 1세대로 , 1세대 드래곤 커브를 2세대로 ... n세대 까지 만들어 주어야 한다.

주어진 예제를 잘 살펴보면 맨 마지막에 그려진 점을 기준으로 시계방향으로 90' 회전하는 것을 알 수 있다.

그렇다면 벡터에 담긴 점들을 마지막 점 기준으로 회전하여 다시 벡터에 담으면 된다.

이를 n번 반복하면 n세대 드래곤 커브가 완성된다.

다만 주의할점.. 벡터의 첫 원소부터 회전 후 담게되면 맨 마지막점이 바뀐다.

따라서 구현할 때 맨 마지막에서 두번째 원소먼저 회전하도록 구현하였다.

 

회전할 때 행렬의 회전을 이용하였다. 참고 : https://ko.wikipedia.org/wiki/%ED%9A%8C%EC%A0%84%EB%B3%80%ED%99%98%ED%96%89%EB%A0%AC

회전변환행렬 - 위키백과, 우리 모두의 백과사전

좌표평면과 배열을 잘 조합해서 회전행렬 식으로 만들어보면 (x,y) => (-y,x)가 됨을 알 수 있다.

하지만 여기서 문제점.. 이 식은 (0,0)을 기준으로 만든 식이다. 

따라서 구현할 때 (이동할 좌표 : d, 마지막 좌표 : d' 이라고 해보자)

(d.x - d'.x , d.y - d'.y)를 회전 한 후에 (d.x + d'.x, d.y + d'.y)를 해주면 이동이 된다.

간단히 설명하자면 (0,0)을 기준으로 돌리기 위한 연산이다. (한번에 돌리는 방법이 있다면 알려주세용...ㅜ.ㅜ)

이를 반복하면 n세대 드래곤커브를 얻을 수 있다.

이제 만들어진 드래곤커브들이 모두 map배열에 찍히게 되고 find()함수로 답을 구하면 끝.