[Baekjoon]15685.드래곤 커브

15685.드래곤 커브

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

15685번: 드래곤 커브

---

드래곤 커브가 그리는 방향의 규칙을 찾아내는 것이 핵심인 문제다. 이런 문제가 나오면 반드시 직접 그려보면서 규칙을 찾아봐야겠다. 

 

먼저 0방향으로 시작해서 방향의 규칙을 찾아보면

0세대 : 0

1세대 : 0-1

2세대 : 0-1-2-1

3세대 : 0-1-2-1-2-3-2-1

4세대 : 0-1-2-1-2-3-2-1-2-3-0-3-2-3-2-1

 

이런 방향으로 선분이 계속 그려지게 된다. 직관적으로 생각했을때 다음세대의 커브는 이전세대 커브에 같은 커브를 방향만 바꿔서 이어붙인 것이므로 길이는 2배가 되고 방향도 이전 세대 커브와 같은 규칙을 가질 것이라고 생각할 수 있다. 

 

세대를 거치면서 길이가 1,2,4,8,16...으로 두배씩 커지는 것을 볼 수 있고 방향에서도 규칙을 찾을 수 있다.

0세대 : 0

1세대 : 0 / 1

2세대 : 0-1 / 2-1

3세대 : 0-1-2-1 / 2-3-2-1

4세대 : 0-1-2-1-2-3-2-1 / 2-3-0-3-2-3-2-1

 

n세대 = n-1세대 / n-1세대 역방향 +1 씩

 

방향 3의 경우 1을 더하면 0된다.(0,1,2,3 네 방향이므로)

 

위 규칙을 이용해서 입력으로 주어지는 드래곤 커브의 방향값을 저장할 배열 dir을 만들고 그 배열에 저장된 방향에 따라 map에서 그려주면 된다. 역방향 규칙이 있어서 stack을 이용해서 푸는 풀이도 있는것 같았다. 나는 단순히 for문을 이용해서 푸는 풀이를 참고했다. 

 

dir이 다 만들어졌으면 map에서 시작 좌표에서부터 dir배열에서 0번째부터 차례대로 꺼내면서 해당 map좌표값을 ++해준다. 나중에 사각형 개수를 셀 때 map좌표값이 0이 아닌 곳은 드래곤 커브가 지나는 곳이라고 생각하면 된다. 

private static void dragonCurve(int x, int y, int d, int g) {

		ArrayList dir = new ArrayList<>();
		dir.add(d);

		for (int i = 1; i <= g; i++) { // g세대까지 방향값 저장
			int size = dir.size() - 1;
			for (int j = size; j >= 0; j--) {
				dir.add((dir.get(j) + 1) % 4);
			}
		}

		map[y][x]++; // 드래곤 커브가 그려지는 좌표 체크
		for (int i = 0; i < dir.size(); i++) {
			x = x + dx[dir.get(i)];
			y = y + dy[dir.get(i)];
			map[y][x]++;
		}

	}

<전체코드>