[백준_15685]_드래곤 커브

4069 단어 psGraphGraph

Link

문제

드래곤 커브는 다음과 같은 세 가지 속성을 갖는다.

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);
          }
      }

  }
}

좋은 웹페이지 즐겨찾기