[백준_15685]_드래곤 커브
문제
드래곤 커브는 다음과 같은 세 가지 속성을 갖는다.
1.시작점 2.시작 방향 3.세대
1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다.
0,0 점에서 1,0을 이은 선이 0세대. 0세대 선 1,0을 잡고 시계방향으로 90 돌리면 1,0 점에서 1,-1 이라는 선이 생기며 여기 까지 이어진 선들이 1세대 이다.
이런 규칙을 토대로 선들이 그려지는데 선들이 그려짐으로 인해 사각형을 이룰 수 는 개수는 얼마인지 구하는 문제이다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)
세대를 거듭할 수록 크기는 2배가 되는 것을 알 수 있으며 이전 세대를 기반으로 회전 시킨다는 것을 알수 있다.
0세대 : 오른쪽
1세대 : 0세대 + 위
2세대 : 1세대 + 왼쪽 + 위
.
.
.
.
이전세대 기반으로 방향이 만들어지는 것을 알 수 있다. 좀 더 구체적으로 보면
1세대는 기존의 0세대의 방향+ 위 가 더해졌는데. '위'라는 것이 어떻게 만들어졌을까 가 여기서 핵심이다.
0세대의 이전세대의 마지막 방향부터해서 처음방향까지 반시계 방향으로 회전하는 규칙을 갖는다.
0세대 : 오른쪽
1세대 : 오른쪽(0세대)+위쪽
2세대 : 오른쪽+위쪽 (1세대 )+ 왼쪽 + 위쪽
왼쪽+위쪽은 2세대의 위쪽 방향을 반시계 회전 왼쪽,오른쪽 방향을 반시계로 회전하여 위쪽이 만들어 진것이다.
이전에 말한 이전세대를 기반으로 거꾸로 반시계 방향을 회전하며 다음세대를 만들 수 있다는 것이다.
✔사각형의 유무는 사각형의 각 꼭짓점의 배열의 칸 안에 표시하면 된다.
이런식으로 각 선이 만들어지면 각 좌표를 꼭지점이라 생각하면 선을 계속 그려진 뒤
마지막에 배열의 크기만큼 순회하면
i,j
i+1,j
i,j+1
i+1,j+1
이 모두 true 인지 확인하여 count 해주면 된다.
package Thur_Sunday_aWeek_Al.SAMSUNG;
import java.util.ArrayList;
import java.util.Scanner;
public class dragonCurve {
static int dx[]={0,-1,0,1};
static int dy[]={1,0,-1,0}; // 오,위,왼,아래
static int y,x,d,g;
static boolean map[][]=new boolean[101][101];
static ArrayList<Integer> direc;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for (int i = 0; i <n ; i++) {
y=sc.nextInt();
x=sc.nextInt();
d=sc.nextInt();
g=sc.nextInt();
direc= new ArrayList<>();
direc.add(d);
curve(g);
draw(x,y);
}
int cnt=0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if(map[i][j] && map[i+1][j]&& map[i][j+1] && map[i+1][j+1])
cnt++;
}
}
System.out.println(cnt);
}
static void draw(int x,int y)
{
map[x][y]=true;
int nx=x;
int ny=y;
for (int i = 0; i < direc.size(); i++) {
int d=direc.get(i);
nx+=dx[d];
ny+=dy[d];
map[nx][ny]=true;
}
}
private static void curve(int genertaions) {
for (int i = 0; i < genertaions; i++) { // 몇세대 까지 그려라.
int size=direc.size();
for (int j = size-1; j >=0 ; j--) {
direc.add((direc.get(j)+1)%4);
}
}
}
}
Author And Source
이 문제에 관하여([백준_15685]_드래곤 커브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@admin1194/백준15685드래곤-커브저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)