[골드3] 15685. 드래곤 커브 (Java)
https://www.acmicpc.net/problem/15685
15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커
www.acmicpc.net
드라군 커브 아닌가
※ 문제를 요약하면 아래와 같습니다.
▶ 드래곤 커브는 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의
( 시작점, 시작 방향, 세대 )
▶ 좌표 평면의 x축은 → 방향, y축은 ↓ 방향
▶ 드래곤 커브는 아래와 같이 진행
1. 0세대 드래곤 커브는 임의의 점 (x,y)에서 시작하여 임의의 방향(동,북,서,남) 으로 한칸 이동한 점을 이은 선분
2. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전 시킨 다음,
0세대 드래곤 커브의 끝 점에 붙인 것
3. 2세대 드래곤 커브도 1세대를 만든 방법과 동일하게 생성 (파란색이 새로 추가된 선분)
4. 임의의 세대 G세대 까지 위의 과정을 반복
▶ 위와 같이 드래곤 커브를 생성 하였을 때 1x1크기의 정사각형의 네 꼭짓점이 드래곤 커브의 일부인 경우인 갯수
ex) Input- 1 : 정답 4개
▶ Input : 첫번째 줄에 드래곤 커브의 개수 N(1 <= N <= 20)
둘째 줄부터 N개의 줄에 드래곤 커브 정보, x,y,g,d 입력
x,y = 드래곤 커브의 시작점
d = 0,1,2,3 (동, 북, 서, 남)
g = 세대
▶ Output : 크기가 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 갯수 출력
◈ Input - 1
3
3 3 0 1
4 2 1 3
4 2 2 1◈ Output - 1
4◈ Input - 2
4
3 3 0 1
4 2 1 3
4 2 2 1
2 7 3 4◈ Output - 2
11◈ Input - 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◈ Output - 3
8◈ Input - 4
4
50 50 0 10
50 50 1 10
50 50 2 10
50 50 3 10◈ Output - 4
1992◎ 코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.
▶ 맵의 크기를 boolean 형태의 101x 101 크기로 선언 ( 문제에서 0~100까지의 x,y 좌표 값 적용 )
▶ 좌표 관리 중 혼란 방지를 위해 x== col , y==row로 변수 활용
▶ 방향 탐색은 델타탐색으로 순서를 동,북,서,남으로 설정
▶ 드래곤 커브의 과정에서 발견 가능한 새로운 규칙을 아래와 같이 정리
1. 0세대에서 1세대로 변하는 과정
2. 1세대에서 2세대로 변하는 과정
3. 현 세대의 마지막 끝점의 방향부터 최초의 끝점 방향까지
반시계 방향으로 90도 돌려가면서 커브의 끝점에 이어 붙이면 다음 세대가 완성되는 것을 확인
▶ 각 세대 별 방향을 저장하기 위한 ArrayList 생성 ( 코드 내 listCurve )
▶ 새로운 규칙 구현 과정
1. 최초의 방향을 ArrayList에 추가
2. 입력받은 G가 0보다 클 때까지 각 세대 탐색 ( 주어진 모든 세대가 탐색이 될 때 까지 - 코드 내 dragonCurve 함수)
3. 현 세대의 가장 나중에 추가된 방향부터 최초의 방향까지 +1된 값을 추가 ( 방향+1 == 반시계방향)
4. 각 세대 탐색이 끝난 후 최초 시작점 부터 ArrayList에 저장된 방향들을 지나가면서 true로 표시 ( MarkCurve함수 )
5. 주어진 입력 값에 대한 모든 1~4번 과정을 종료 후 1x1 정사각형 꼭짓점을 갖는 갯수 카운트 (코드 내 getRect 함수)
▶ 정사각형 꼭짓점을 갖는 갯수 출력
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, X, Y, D, G;
static boolean[][] barrMap;
static ArrayList<Integer> listCurve;
// 동, 북, 서, 남 == 0,1,2,3
static int[] dr = {0, -1, 0, 1};
static int[] dc = {1, 0, -1, 0};
public static void main(String[] args) throws NumberFormatException, IOException {
// 대박 대박 대박
System.setIn(new FileInputStream(Main.class.getResource("input.txt").getPath()));
// TODO Auto-generated method stub
BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// 커브 횟수 받구
N = Integer.parseInt(bReader.readLine());
barrMap = new boolean[101][101];
for(int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(bReader.readLine());
X = Integer.parseInt(st.nextToken());
Y = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
listCurve = new ArrayList<>();
// 0 세대는 미리 추가
listCurve.add(D);
dragonCurve();
}
int nResult = getRect();
bWriter.write(String.valueOf(nResult));
bWriter.close();
}
private static int getRect() {
int nRectCount = 0;
// 1x1 정사각형 일 때마다 카운트
for(int i = 0; i < 100; i++) {
for(int j = 0; j < 100; j++) {
if(barrMap[i][j] && barrMap[i][j+1]
&& barrMap[i+1][j] && barrMap[i+1][j+1])
nRectCount++;
}
}
return nRectCount;
}
private static void dragonCurve() {
// 세대 별로 규칙 적용
// 세대가 지날 수록 LIFO 구조 +1을 쌓는다.
while(G > 0) {
int nSize = listCurve.size();
for(int i = nSize-1; i >=0 ; i--) {
// 반시계 방향 90도면 방향 +1과 동일
int nDirection = listCurve.get(i) + 1;
if(nDirection > 3)
nDirection -= 4;
listCurve.add(nDirection);
}
G--;
}
MarkCurve();
}
// 토대로 표시해준 방향을 커브가 지나간 곳을 true 표시해주자
private static void MarkCurve() {
int nRow = Y;
int nCol = X;
barrMap[nRow][nCol] = true;
for(int i = 0; i < listCurve.size(); i++) {
// 커브가 지나간 점들을 다 true 표시해주공
nRow += dr[listCurve.get(i)];
nCol += dc[listCurve.get(i)];
if(!barrMap[nRow][nCol])
barrMap[nRow][nCol] = true;
}
}
}Good Luck! (피드백 감사합니다!)