(JAVA) 백준 15685 번 : 드래곤 커브

 

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

15685번: 드래곤 커브

 

 

 

시뮬레이션 문제.

 

삼성 SW 기출 문제이다.

 

 

 

규칙만 찾으면 쉬운 문제다.

 

 

규칙은 같으나

이를 구현하는 알고리즘은 다양한데,

 

내 방법이 좋은 편은 아니지만

 

코드를 읽기에는 좋은 방법이다.

 

 

 

 

노트10으로 직접 그려보았다!

위 그림을 보면, n 세대 드래곤 커브가 시작 점부터 어느 방향으로 진행되고 있는지 알 수 있다.

 

처음에 0(→) 으로 시작했다면, 

다음 세대에는 → ↑ 로 진행된다.

 

그 다음 세대에는 →↑←↑ 로 진행된다.

 

 

규칙을 찾았는가?

 

다음 그림을 보자.

방향을 왼쪽 최상단에 그린 것과 같이 0 ~ 3으로 정의를 하고,

 

드래곤 커브의 방향을 Array로 나타내보면

 

 

0 세대 : 1

1 세대 : 1, 0

2 세대 : 1, 0, 3, 0

3 세대 : 1, 0, 3, 0, 3, 2, 3, 0

 

이다.

 

 

 

즉, K세대 드래곤 커브의 방향 Array는 

 

 

K - 1세대 드래곤 커브의 방향 Array 에서

역순으로 탐색하며 방향 - 1 % 4 (방향이 0이면 4로 리셋) 의 값을 push(맨 끝에 집어넣기) 한 결과와 같다.

 

 

이를 위해 LinkedList를 사용했고,

 

역순으로 탐색 시

 

해당 값은 offerFirst() 를 사용해서 맨 앞에 push한 후,

방향 - 1 % 4 한 값은 offerLast() 를 사용해서 맨 뒤에 push하면 

 

순서에 맞게 삽입된다.

 

 

그렇게 되면 각 세대의 Array 크기는

2^k 와 같다. (= 이전 Array 크기의 2배)

 

 

 

 

이를 DP로 미리 저장해놨다.

 

 

그 이유는 입력 값으로 받는 최대 세대 크기 값이 10으로 주어졌고,

여러 드래곤 커브 값을 input으로 받으며,

한 번 구해놓은 방향 Array를 활용해 드래곤 커브를 그릴 수 있기 때문이다.

 

 

또한, 

 

4개의 방향 각각을 계산해서 저장할 필요 없이

한 개의 시작 방향만 저장해두고

 

다른 시작 방향을 구하려고 하면

각 방향 값에서 그 방향의 index를 더하면 된다.

 

 

예를 들어,

 

 

시작 방향 0(↑)을 구한 다음

 

시작 방향 2(↓)의 드래곤 커브를 구하고 싶으면

 

시작 방향 0의 Array 값에서 2를 더하면 된다.

 

 

 

 

이 걸 알고

알고리즘으로 구현하면 

바로 문제를 해결할 수 있다.

 

 

*** 참고로 나는 Direction을 위 - 오른쪽 - 아래 - 왼쪽 으로 가정하고 만들었지만

문제에서 정한 Direction과는 달라서 애먹었었다.

그래서 별도의 함수를 만들어 변환시켜서 작업했다.

 

백준 문제에서 요구사항

 

 

 

 

또,

 

 

드래곤 커브로 그린 직사각형을 찾기 위해

2차원 boolean 배열을 만들고,

 

드래곤 커브에 포함되는 좌표의 boolean 값은 True로 변경 하는 작업을 사전에 진행하고,

 

점을 하나씩 탐색하며

정사각형 4개의 꼭짓점 boolean 값이 전부 True이면 정사각형을 그린 것으로 간주했다.

 

 

 

 

매커니즘은 따로 작성하지 않고

 

위 해설과 밑의 소스코드(+ 주석)을 참고하면 해결할 수 있을 것이다.

 

 

 

 

 

감사합니다!

좋은 하루 보내세요 ㅎㅎ!

 

 

소스코드

---