[백준/자바] 15685 드래곤 커브

15685 드래곤 커브 사진 클릭시 문제로 이동

---

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다.

아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다.

끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다.

아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다.

이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다.

드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다.

x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다.

드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

예제 입력 1

3
3 3 0 1
4 2 1 3
4 2 2 1

예제 출력 1

4

예제 입력 2

4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4

예제 출력 2

11

예제 입력 3

10
5 5 0 0
5 6 0 0
5 7 0 0
5 8 0 0
5 9 0 0
6 5 0 0
6 6 0 0
6 7 0 0
6 8 0 0
6 9 0 0

예제 출력 3

8

예제 입력 4

4
50 50 0 10
50 50 1 10
50 50 2 10
50 50 3 10

예제 출력 4

1992

힌트

예제 1	예제 2

---

설명

드래곤 커브를 구하는 문제다.

문제를 살펴보면 규칙을 볼 수 있다.

우선 방향은 다음과 같다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

static int dxy[][] = {{0,1}, {-1,0}, {0,-1}, {1,0}};  // → - 0, ↑ - 1, ← - 2, ↓ - 3

예제 그림을 순서대로 살펴보자.

횟수 0 : 

0

횟수 1:

0 1

앞의 0의 방향의 +1한 값인 1이 붙은 것을 볼 수 있다.

횟수 2:

0 1 2 1

앞의 방향이었던 0 1을 뒤에서 1부터 +1인 값인 2와 1이 차례로 붙은 것을 볼 수 있다.

여기서 규칙을 유추해볼 수 있는데,

앞에서 나온 방향들의 값을 뒤에서 부터 살피며 +1한 값을 붙여주는 것을 알 수 있다.

횟수 3:

0 1 2 1 2 3 2 1

앞에서 유추한 규칙처럼 앞에서 나온 방향들의 값을 뒤에서 부터 살피며 +1한 값을 붙여주는 것을 알 수 있다.

규칙 코드는 다음과 같다.

for(int i = 0; i < g+1; i++) {
	for(int j = dir.size()/2; j < dir.size(); j++) {
		end.x = end.x + dxy[dir.get(j)][0];
		end.y = end.y + dxy[dir.get(j)][1];
		visited[end.x][end.y] = true;
	}

	ArrayList<Integer> temp = new ArrayList<>(); // 새로 붙일 방향을 잠시 저장할 변수
	for(int j = dir.size()-1; j > -1; j--) { // 원래 가진 방향을 뒤에서 부터 살펴봄
		temp.add((dir.get(j)+1)%4); // 방향의 index는 0 ~3이기 때문에 %4
	}
			
	for(int j : temp) { // 새로 붙인 방향을 dir에 붙여주기
		dir.add(j);
	}
}

마지막으로 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것을 확인하기 위한 코드는 다음과 같이 2중 for문을 돌며 4개의 꼭짓점을 확인한다.

이때, 주의해야할 점은 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이기 때문에 for문은 100미만일때까지다.

for(int i = 0; i < 100; i++) {
	for(int j = 0; j < 100; j++) {
		if(visited[i][j] && visited[i+1][j] && visited[i][j+1] && visited[i+1][j+1]) {
			answer++;
		}
	}
}

코드