[백준 알고리즘, 시뮬레이션] 삼성 코딩 테스트 문제 :: 15686번 드래곤 커브 자바 풀이

이 문제도 역시 시뮬레이션 문제에요

삼성 코딩 테스트 문제는 시뮬레이션 문제가 많은것 같아요

구현 사항이 주어졌을때 그것을 그대로 구현할 수 있느냐 없느냐??

그걸 많이 테스트 하나봐요

 

문제는 아래에서 풀어보실 수 있어요

https://www.acmicpc.net/problem/15685

 

이번 문제는 class 두개를 선언해서 코딩했어요

Point 클래스와 Dragon 클래스

Point 클래스는 말그대로 점에 대한 정보를 담는 클래스이고

Dragon 클래스는 드래곤 점의 정보와 방향 세대를 나타내요

맵에 처음 드래곤 커브의 시작점을 찍었는데요 (map[y][x] = 1)

여기서 문제의 x,y와 저희가 기본적으로 생각하는 xy의 축이 반대로 되어있어요!! (이 부분이 key point)

 

먼저 initDragon 함수를 통해서 처음점을 통해 그 다음 점(두번째 점)을 찍어주었어요

그리고 MakeDragon을 통해서 드래곤 커브를 하나씩 그려나갔어요

 

MakeDragon 함수에서는 끝점을 기준으로 먼저 정렬했어요. 끝점을 기준으로 돌려야 되기 때문이에요

무슨 말이냐하면 끝점을 축의 기준 (0,0)으로 잡았어요

만약 끝점이 (3,3)이었다면 (0,0)으로 바꿔주고 나머지 점들을 x축으로 -3, y축으로 -3만큼 해줬어요

그렇게 정렬을 하고 90도 회전을 시켰어요. 회전은 삼각함수 아시나요??

cos(x)	-sin(x)
sin(x)	cos(x)

위와 같은 행렬을 곱해주는 거에요. 90도를 회전시키는 거니까 x가 90도가 되서 아래처럼 되요

0	-1	x
1	0	y

즉 x' = -y   /   y'=x 가 되요 이렇게 90도 회전을 해주었답니다

그러고 끝점을 기준으로 하면서 값들이 바뀌었기 때문에 다시 원래대로 변환해줍니다!!

그러면 이렇게 드래곤 커브의 한 세대를 끝낸거에요!!

위와 같이 모든 드래곤 커브를 만든다음에 색칠하고를 반복하여 답을 구하였습니다

이 문제는 회전에 대해 알거나 거꾸로된 축 문제를 풀어보신 분이라면 풀만 하겠지만

저는 이러한 문제는 처음이었기에 쉽지 않았어요 ㅠㅠㅠ

그래도 고민 끝에 풀 수 있었답니다!!

 

 

아래 코드 올려둔 깃허브 주소도 있으니 참고하세요!!

https://github.com/wlgh325/BOJ_answer/tree/master/15685(Dragon%20Curve)

wlgh325/BOJ_answer

<백준 온라인 저지 15685번 드래곤 커브 자바 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;


class Point{
	int x;
	int y;

	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

class Dragon{
	ArrayList<Point> pnts;
	int dir;
	int gen;

	Dragon(int dir, int gen){
		pnts = new ArrayList<>();
		this.dir = dir;
		this.gen = gen;
	}
}

class Main {
	static ArrayList<Dragon> dragons;
	static int[][] map;
	static int height = 101;
	static int width = 101;
	

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		int dragonNum = Integer.parseInt(input);
		
		dragons = new ArrayList<>();
		map = new int[height][width];

		for(int i=0; i<dragonNum; i++){
			String input2 = br.readLine();
			String[] temp2 = input2.split(" ");
			
			int x = Integer.parseInt(temp2[0]);
			int y = Integer.parseInt(temp2[1]);
			int dir = Integer.parseInt(temp2[2]);
			int gen = Integer.parseInt(temp2[3]);

			dragons.add(new Dragon(dir, gen));
			dragons.get(i).pnts.add(new Point(x,y));
			// 2,4 -> 4,2
			map[y][x] = 1;
		}

		
		for(int i=0; i<dragonNum; i++){
			initDragon(dragons.get(i));
			MakeDragonCurve(dragons.get(i));
		}

		System.out.println(getBoxNum());
	}

	// 00 01 10 11
	// 01 02 11 12
	static int getBoxNum(){
		int count = 0;
		for(int i=0; i<height-1; i++){
			for(int j=0; j<width-1; j++){
				if(map[i][j] == 1 && map[i][j+1] == 1 && map[i+1][j] == 1 && map[i+1][j+1] == 1){
					count++;
				}
			}
		}

		return count;
	}

	static void initDragon(Dragon dragon){
		Point pnt = dragon.pnts.get(0);

		switch(dragon.dir){
			case 0:
				dragon.pnts.add(new Point(pnt.x+1, pnt.y));
				map[pnt.y][pnt.x + 1] = 1;
				break;
			case 1:
				dragon.pnts.add(new Point(pnt.x, pnt.y-1));
				map[pnt.y - 1][pnt.x] = 1;
				break;
			case 2:
				dragon.pnts.add(new Point(pnt.x-1, pnt.y));
				map[pnt.y][pnt.x - 1] = 1;
				break;
			case 3:
				dragon.pnts.add(new Point(pnt.x, pnt.y+1));
				map[pnt.y + 1][pnt.x] = 1;
		}
	}

	static void MakeDragonCurve(Dragon dragon){
		// gen번 회전 -> gen세대
		for(int i=0; i<dragon.gen; i++){
			rotate(dragon);
		}
	}

	static void rotate(Dragon dragon){
		ArrayList<Point> temp = dragon.pnts;

		Point endPoint = temp.get(temp.size() - 1);
		ArrayList<Point> tempList = new ArrayList<>();
		
		// 끝점을 기준으로 정렬
		for(int i=0; i<temp.size(); i++){
			int x = temp.get(i).x;
			int y = temp.get(i).y;

			x -= endPoint.x;
			y -= endPoint.y;

			tempList.add(new Point(x,y));
		}		
		dragon.pnts = tempList;
		rotate90(dragon);

		// 원래대로 돌려놓기
		for(int i=0; i<dragon.pnts.size(); i++){
			dragon.pnts.get(i).x += endPoint.x;
			dragon.pnts.get(i).y += endPoint.y;
		}
		paint(dragon);
	}

	static void rotate90(Dragon dragon){
		ArrayList<Point> temp = dragon.pnts;
		int size = temp.size();
		for(int i=size-2; i>=0; i--){
			int x = 0 * temp.get(i).x + -1 * temp.get(i).y;
			int y = 1 * temp.get(i).x + 0 * temp.get(i).y;
			temp.add(new Point(x,y));
		}
		
	}

	static void paint(Dragon dragon){
		ArrayList<Point> arrList = dragon.pnts;

		for(int i=0; i<arrList.size(); i++){
			map[arrList.get(i).y][arrList.get(i).x] = 1;
		}
	}
}

2019/10/28 - [알고리즘/백준 알고리즘] - [백준 온라인 저지(BOJ), 브루트 포스] 삼성 코딩 테스트 문제 :: 15683번 감시 자바 풀이

2019/10/27 - [알고리즘/백준 알고리즘] - [백준 알고리즘, ] 삼성 코딩 테스트 문제 :: 14891번 톱니바퀴 자바 풀이

2019/10/26 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 다이나믹 프로그래밍] 삼성 코딩 테스트 문제 기출 :: 14501번 퇴사 자바 풀이