[알고리즘] 드래곤 커브 (백준 15685번)

15685번: 드래곤 커브

 삼성 소프트웨어 역량 테스트 기출 문제이다. 특정 점을 기준으로 도형을 회전시키는 전형적인 시뮬레이션 문제이다. 예전에 문제를 보다가 도저히 어떻게 해야할지 감이 안 잡혀서 안 풀었었는데 이번에 새로 보니 생각보다 어렵지 않았다.

 보통 도형 회전 문제는 잘 보면 일종의 규칙을 발견할 수 있다.

 

Solution

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {


	static int map[][] = new int[101][101];

	public static void solution() throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		ArrayList[] dragonCurves = new ArrayList[N];

		for(int i = 0;i < N;i++)
		{
			dragonCurves[i] = new ArrayList<Position>();

			String[] list = br.readLine().split(" ");
			int x = Integer.parseInt(list[0]);
			int y = Integer.parseInt(list[1]);
			int d = Integer.parseInt(list[2]);
			int g = Integer.parseInt(list[3]);

			dragonCurves[i].add(new Position(x, y));
			makeDragonCurve(dragonCurves[i], d, g);
		}

		int count = 0;

		for(int i = 0;i < 100;i++)
		{
			for(int j = 0;j < 100;j++)
			{
				if(map[i][j] == 1 && map[i+1][j] == 1 && map[i][j+1] == 1 && map[i+1][j+1] == 1)
					count++;
			}
		}

		bw.write(count+"");
		bw.close();
		br.close();
	}

	public static void makeDragonCurve(ArrayList<Position> dragonCurve, int d, int g)
	{
		//0세대 드래곤 커브 만들기
		map[dragonCurve.get(0).x][dragonCurve.get(0).y] = 1;

		//x증가 방향 -> 남쪽
		if(d == 0)
		{
			map[dragonCurve.get(0).x + 1][dragonCurve.get(0).y] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x + 1, dragonCurve.get(0).y));
		}
		//y감소 방향 -> 서쪽
		else if(d == 1)
		{
			map[dragonCurve.get(0).x][dragonCurve.get(0).y - 1] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x, dragonCurve.get(0).y - 1));
		}
		//x감소 방향 -> 북쪽
		else if(d == 2)
		{
			map[dragonCurve.get(0).x - 1][dragonCurve.get(0).y] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x - 1, dragonCurve.get(0).y));
		}
		//y증가 방향 -> 동쪽
		else
		{
			map[dragonCurve.get(0).x][dragonCurve.get(0).y + 1] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x, dragonCurve.get(0).y + 1));
		}

		//g세대 만큼
		for(int i = 0;i < g;i++)
		{
			//기준점은 끝점 기준
			int size = dragonCurve.size();
			int ref_x = dragonCurve.get(size - 1).x;
			int ref_y = dragonCurve.get(size - 1).y;

			//회전하게 되면 첫 시작점의 회전점이 다음 끝점이 되어야함
			for(int j = size - 2;j >= 0;j--)
			{
				int turn_pos[] = turnPosition(ref_x, ref_y, dragonCurve.get(j).x, dragonCurve.get(j).y);
				map[turn_pos[0]][turn_pos[1]] = 1;
				dragonCurve.add(new Position(turn_pos[0], turn_pos[1]));
			}
		}

	}

	public static int[] turnPosition(int ref_x, int ref_y, int x, int y)
	{
		int turn_pos[] = new int[2];

		//주의 : 반시계 방향으로 회전 (이유 : 예시의 좌표계는 y가 가로줄 담당, x가 세로줄 담당 -> 여기서는 x가 가로줄 담당, y가 세로줄 담당이어서 거꾸로

		//+ + -> + -
		if(ref_x > x && ref_y > y)
		{
			turn_pos[0] = ref_x + Math.abs(ref_y - y);
			turn_pos[1] = ref_y - Math.abs(ref_x - x);
		}
		//+ - -> - -
		else if(ref_x > x && ref_y <= y)
		{
			turn_pos[0] = ref_x - Math.abs(ref_y - y);
			turn_pos[1] = ref_y - Math.abs(ref_x - x);

		}
		//- - -> - +
		else if(ref_x <= x && ref_y <= y)
		{
			turn_pos[0] = ref_x - Math.abs(ref_y - y);
			turn_pos[1] = ref_y + Math.abs(ref_x - x);
		}
		//- + -> + +
		else
		{
			turn_pos[0] = ref_x + Math.abs(ref_y - y);
			turn_pos[1] = ref_y + Math.abs(ref_x - x);
		}

		return turn_pos;
	}

	static class Position{
		int x, y;

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

	public static void main(String[] args) {
		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}

 전체 코드이다.

 

 우선 입력 정보를 받아서 0세대 드래곤커브를 만드는 것까진 별 거 아니다. 1세대부터는 현재 드래곤 커브의 끝점을 기준으로 시계방향으로 90도를 회전시킨 도형을 끝점에 붙여야 한다.

 

 위의 예시와 같은 경우이다. 1세대의 끝점은 (1, -1)이고 해당 점을 기준으로 1세대 드래곤 커브를 90도 회전시킨 도형을 (1, -1)에 붙인다. 그럼 2세대 드래곤 커브가 완성되고 현재 2세대 드래곤 커브의 끝점은 (0, -2)가 된다.

 즉 기존 시작점 (0, 0)이 회전한 점이 새로운 끝점이 되는 것이다. 해당 부분을 구현한 것이 아래 코드다.

	public static void makeDragonCurve(ArrayList<Position> dragonCurve, int d, int g)
	{
		//0세대 드래곤 커브 만들기
		map[dragonCurve.get(0).x][dragonCurve.get(0).y] = 1;

		//x증가 방향 -> 남쪽
		if(d == 0)
		{
			map[dragonCurve.get(0).x + 1][dragonCurve.get(0).y] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x + 1, dragonCurve.get(0).y));
		}
		//y감소 방향 -> 서쪽
		else if(d == 1)
		{
			map[dragonCurve.get(0).x][dragonCurve.get(0).y - 1] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x, dragonCurve.get(0).y - 1));
		}
		//x감소 방향 -> 북쪽
		else if(d == 2)
		{
			map[dragonCurve.get(0).x - 1][dragonCurve.get(0).y] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x - 1, dragonCurve.get(0).y));
		}
		//y증가 방향 -> 동쪽
		else
		{
			map[dragonCurve.get(0).x][dragonCurve.get(0).y + 1] = 1;
			dragonCurve.add(new Position(dragonCurve.get(0).x, dragonCurve.get(0).y + 1));
		}

		//g세대 만큼
		for(int i = 0;i < g;i++)
		{
			//기준점은 끝점 기준
			int size = dragonCurve.size();
			int ref_x = dragonCurve.get(size - 1).x;
			int ref_y = dragonCurve.get(size - 1).y;

			//회전하게 되면 첫 시작점의 회전점이 다음 끝점이 되어야함
			for(int j = size - 2;j >= 0;j--)
			{
				int turn_pos[] = turnPosition(ref_x, ref_y, dragonCurve.get(j).x, dragonCurve.get(j).y);
				map[turn_pos[0]][turn_pos[1]] = 1;
				dragonCurve.add(new Position(turn_pos[0], turn_pos[1]));
			}
		}

	}

---

 그 다음은 이제 도형의 회전이다. 정확히는 도형의 회전이 아닌 도형의 꼭지점들의 회전이다. 우선 주의할 점은 예시문에서의 좌표계는 y가 가로줄, x가 세로줄을 담당하고 있다. 그렇기 때문에 x가 가로줄, y가 세로줄을 담당하고 있는 좌표계로 변환할 때는 시계방향 회전이 아닌 반시계방향으로 회전해야한다.

 

 점들의 회전은 4가지 경우로 나눌 수 있다.

1. 기준점 x보다 회전점의 x가 큰 경우 &&  기준점 y보다 회전점의 y가 큰 경우 (+ +)
2. 기준점 x보다 회전점의 x가 큰 경우 && 기준점 y보다 회전점의 y가 작은 경우 (+ -)
3. 기준점 x보다 회전점의 x가 작은 경우 && 기준점 y보다 회전점의 y가 작은 경우 (- -)
4. 기준점 x보다 회전점의 x가 작은 경우 && 기준점 y보다 회전점의 y가 큰 경우 (- +)

  그림으로 나타내면 위와 같다. 회전할 때마다 기준점 x에는 기존 y좌표끼리의 차이를 더하거나 빼야하고, 기준점 y에는 기존 x좌표끼리의 차이를 더하거나 빼면 된다.

	public static int[] turnPosition(int ref_x, int ref_y, int x, int y)
	{
		int turn_pos[] = new int[2];

		//주의 : 반시계 방향으로 회전 (이유 : 예시의 좌표계는 y가 가로줄 담당, x가 세로줄 담당 -> 여기서는 x가 가로줄 담당, y가 세로줄 담당이어서 거꾸로

		//+ + -> + -
		if(ref_x > x && ref_y > y)
		{
			turn_pos[0] = ref_x + Math.abs(ref_y - y);
			turn_pos[1] = ref_y - Math.abs(ref_x - x);
		}
		//+ - -> - -
		else if(ref_x > x && ref_y <= y)
		{
			turn_pos[0] = ref_x - Math.abs(ref_y - y);
			turn_pos[1] = ref_y - Math.abs(ref_x - x);

		}
		//- - -> - +
		else if(ref_x <= x && ref_y <= y)
		{
			turn_pos[0] = ref_x - Math.abs(ref_y - y);
			turn_pos[1] = ref_y + Math.abs(ref_x - x);
		}
		//- + -> + +
		else
		{
			turn_pos[0] = ref_x + Math.abs(ref_y - y);
			turn_pos[1] = ref_y + Math.abs(ref_x - x);
		}

		return turn_pos;
	}

 

---

 마지막으로 전체 반복문을 돌면서 map[i][j], map[i+1][j], map[i][j+1], map[i+1][j+1]이 모두 1인 경우라면 사각형의 꼭지점이 모두 드래곤 커브라는 뜻이기 때문에 count를 증가시키면서 사각형의 갯수를 세면 된다.

int count = 0;

for(int i = 0;i < 100;i++)
{
	for(int j = 0;j < 100;j++)
	{
		if(map[i][j] == 1 && map[i+1][j] == 1 && map[i][j+1] == 1 && map[i+1][j+1] == 1)
        	count++;
	}
}

bw.write(count+"");