문제링크 : https://www.acmicpc.net/problem/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()함수로 답을 구하면 끝.
'Algorithm' 카테고리의 다른 글
백준 - 1422번(숫자의 신) / C++ (0) | 2021.02.22 |
---|---|
프로그래머스 - 가장 큰 수 / C++ (0) | 2021.02.22 |
프로그래머스 - Summer/Winter Coding(2019)(멀쩡한 사각형) / C++ (0) | 2020.10.28 |
백준 - 17070번(파이프 옮기기 1) / C++ (0) | 2020.08.23 |
백준 - 15686번(치킨 배달) / C++ (0) | 2020.07.09 |