[BOJ 15685] 드래곤 커브 - JAVA, Gold3
https://www.acmicpc.net/problem/15685
15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커
www.acmicpc.net
📌구현할 기능 목록📌
1. 드래곤 커브의 개수 그리고 각 커브의 좌표, 방향, 횟수를 입력받는다.
2. 101 x 101 크기의 맵을 생성하여, 특정 좌표가 드래곤 커브로 생긴 선분 위의 좌표인지 확인할 수 있도록
이중 ArrayList 를 생성한다.
3. 각 드래곤 커브에서, 주어진 방향에 맞도록 선분을 추가한다.
4. 주어진 횟수만큼 드래곤 커브를 진행하는 함수를 작성한다.
5. 생성한 드래곤 커브를 101 x 101 이중 ArrayList에 추가시킨다.
6. 3~5번 과정을 드래곤 커브 개수만큼 반복한다.
7. 2번에서 생성한 이중 ArrayLIst의 한 격자(1 x 1 정사각형)의 네 꼭지점이 모두 1인 개수를 출력하는 함수를 작성한다.
🛠주요 로직🛠
드래곤 커브는 기존 선분 집합들을 끝점을 기준으로 시계방향으로 90도 회전시켜야하는 작업이다.
만약 위 그래프처럼 끝점을 원점(0,0)이라고 가정할 때, A를 반시계방향으로 90도 회전시키면
A(3,4) -> A`(-4,3) 으로 좌표가 바뀌는 것을 확인할 수 있다.
즉, x와 y 좌표가 뒤바뀌며, x 좌표가 반전된다.
만약 시계방향으로 90도 회전시킨다면 x,y 좌표가 뒤바뀌고, y 좌표가 반전될 것이다.
단, 우리의 목표는 원점이 아닌 끝점을 기준으로 선분들을 회전시키는 것이다.
따라서 끝점과 각 좌표들의 오차를 구하고, 오차를 사용해 위 공식에 대입한 다음 끝점을 좌표에 더해줘야한다.
예로 A(x1,y1), B(x2,y2) 좌표가 있고, A가 끝점일 때 B가 90도 시계방향으로 회전한다면
B(x,y) = (x1 + y1 - y2, y1 + (x1 - x2)*(-1)) 이 된다.
💻코드 적용💻
1. 드래곤 커브의 개수 그리고 각 커브의 좌표, 방향, 횟수를 입력받는다.
int N = Integer.parseInt(br.readLine());
for(int i=0;i<N;++i){
list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int g = Integer.parseInt(st.nextToken());
...
}
...
2. 101 x 101 크기의 맵을 생성하여, 특정 좌표가 드래곤 커브로 생긴 선분 위의 좌표인지 확인할 수 있도록
이중 ArrayList 를 생성한다.
public static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
for(int i=0;i<=100;++i){
map.add(new ArrayList<>());
for(int j=0;j<=100;++j){
map.get(i).add(0);
}
}
3. 각 드래곤 커브에서, 주어진 방향에 맞도록 선분을 추가한다.
list = new ArrayList<>();
endX = x;
endY = y;
if(d==0){ // 오른쪽
endX=x+1;
}
else if(d==1){ // 위
endY=y-1;
}
else if(d==2){ // 왼쪽
endX=x-1;
}
else if(d==3){ // 아래
endY=y+1;
}
list.add(new Position(x,y));
list.add(new Position(endX,endY));
4. 주어진 횟수만큼 드래곤 커브를 진행하는 함수를 작성한다.
public static void rotate(){
ArrayList<Position> tempList = new ArrayList<>(list);
for(Position position:tempList){
int dx = endX - position.x;
int dy = endY - position.y;
list.add(new Position(endX+dy,endY+dx*(-1)));
}
int tempEndX = endX;
int tempEndY = endY;
endX = tempEndX + tempEndY - tempList.get(0).y;
endY = tempEndY + (tempEndX - tempList.get(0).x)*-1;
}
tempEndX, tempEnxY를 별도로 선언한 이유는 endX, endY를 재정의할 때, endX의 값이 도중에 변경되어 endY의 값 변경에 영향을 미치기 때문이다.
끝점 좌표를 나타내는 endX, endY는 드래곤 커브의 시작점을 기준으로 시계방향 90도 회전시킨 좌표가 끝점이 된다.
5. 생성한 드래곤 커브를 101 x 101 이중 ArrayList에 추가시킨다.
public static void drawRealMap(){
for(Position position:list){
map.get(position.y).set(position.x, 1);
}
}
6. 3~5번 과정을 드래곤 커브 개수만큼 반복한다.
7. 2번에서 생성한 이중 ArrayLIst의 한 격자(1 x 1 정사각형)의 네 꼭지점이 모두 1인 개수를 출력하는 함수를 작성한다.
public static int getResult(){
int answer = 0;
for(int i=0;i<100;++i){
for(int j=0;j<100;++j){
if(map.get(i).get(j)==1 && map.get(i).get(j+1)==1
&& map.get(i+1).get(j)==1 && map.get(i+1).get(j+1)==1){
answer++;
}
}
}
return answer;
}
⌨제출코드⌨
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
public static class Position{
int x;
int y;
public Position(int x,int y){
this.x=x;
this.y=y;
}
}
public static ArrayList<Position> list;
public static int endX=0, endY=0;
public static void rotate(){
ArrayList<Position> tempList = new ArrayList<>(list);
for(Position position:tempList){
int dx = endX - position.x;
int dy = endY - position.y;
list.add(new Position(endX+dy,endY+dx*(-1)));
}
int tempEndX = endX;
int tempEndY = endY;
endX = tempEndX + tempEndY - tempList.get(0).y;
endY = tempEndY + (tempEndX - tempList.get(0).x)*-1;
}
public static void drawRealMap(){
for(Position position:list){
map.get(position.y).set(position.x, 1);
}
}
public static int getResult(){
int answer = 0;
for(int i=0;i<100;++i){
for(int j=0;j<100;++j){
if(map.get(i).get(j)==1 && map.get(i).get(j+1)==1
&& map.get(i+1).get(j)==1 && map.get(i+1).get(j+1)==1){
answer++;
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
for(int i=0;i<=100;++i){
map.add(new ArrayList<>());
for(int j=0;j<=100;++j){
map.get(i).add(0);
}
}
int N = Integer.parseInt(br.readLine());
for(int i=0;i<N;++i){
list = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int g = Integer.parseInt(st.nextToken());
endX = x;
endY = y;
if(d==0){ // 오른쪽
endX=x+1;
}
else if(d==1){ // 위
endY=y-1;
}
else if(d==2){ // 왼쪽
endX=x-1;
}
else if(d==3){ // 아래
endY=y+1;
}
list.add(new Position(x,y));
list.add(new Position(endX,endY));
for(int j=0;j<g;++j){
rotate();
}
drawRealMap();
}
bw.write(getResult()+"\n");
bw.flush();
bw.close();
}
}