[백준] 15685 드래곤 커브

1. 문제

www.acmicpc.net/problem/15685

15685번: 드래곤 커브

2. 접근방법

지금까지 만들어진 그림을

90도 돌려서 기존 그림에 붙이고

또 붙이고 반복해서 만드는 문제

90도를 돌리기 위해 나는 각 점 사이의 관계를 방향으로 설정했다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

정해진 이 좌표에 따라

현재 내점에서 다음 점으로 어떻게 가는지 저장한다.

0,0 과 연결된 1,0으로 가기위해서 -> 으로 가야하기 때문에 0을 저장하고

1,0 과 연결된 1,-1으로 가기위해서는 ↑으로 가야하기 때문에 1을 저장한다.

1,-1에서 다음으로 가는 길이 없기 때문에 우선 -1을 임시로 저장한다.

 

그 다음 회전을 보면

 

기존 1,0 -> 1,-1 이 1방향으로 이동 중이었는데

90도로 회전하면 1, -1  에서 0,-1 로 2방향으로 이동한다.

 

기존 0,0 -> 1,0 은 0방향으로 이동 중이었는데

새롭게 만들어진 0, -1 에서 1방향으로 이동해 0,-2로 이동하고 있다.

 

즉 지금 만들어진 끝점에 기존에 연결된 ( 방향 +1 ) 의 방향으로 이동시키는 것을 반복 시키면 된다.

 

그것을 구현한 코드가

 

이 부분이다.

기존 연결된 방향을 가져와서

end의 방향으로 만들어주고

end에서 방향으로 이동시킨 위치를 새로운 end로 만들어주고

전체 모양을 가지고 있는 list에 집어넣는다.

 

이렇게 드래곤 커브를 모두 맵에 만들어주고

for문으로 모든 맵을 검사하면서 1x1 사각형의 갯수를 구해주면 된다.

3. 자바 코드

package algo;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ15685드래곤커브 {
	static class Point {
		int x, y, pred;
		public Point(int x, int y, int pred) {
			this.x = x;
			this.y = y;
			this.pred = pred;
		}
	}
	static int map[][] = new int[101][101];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			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());
			make_dragon(x, y, d, g);
		}
		int cnt = 0;
		for (int i = 0; i < 100; i++)
			for (int j = 0; j < 100; j++)
				if (check(i, j)) cnt++;
		System.out.println(cnt);
	}
	static boolean check(int x, int y) {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				if (map[x + i][y + j] != 1)
					return false;
		return true;
	}
	static int dr[] = { 0, -1, 0, 1 }, dc[] = { 1, 0, -1, 0 };
	static void make_dragon(int x, int y, int d, int g) {
		List<Point> dot = new ArrayList<Point>();
		dot.add(new Point(y, x, d)); dot.add(new Point(y + dr[d], x + dc[d], -1));
		map[y][x] = 1; map[y + dr[d]][x + dc[d]] = 1;
		for (int gg = 0; gg < g; gg++) {// 세대만큼
			int size = dot.size();
			Point end = dot.get(size - 1);
			for (int i = size - 2; i >= 0; i--) {
				int pred = (dot.get(i).pred + 1) % 4;
				end.pred = pred;
				int row = end.x + dr[pred];
				int col = end.y + dc[pred];
				map[row][col] = 1;
				dot.add(end = new Point(row, col, -1));
			}
		}
	}
}

4. 마치며

90도 돌리는 개념을 생각해내는 것도 꽤나 어려웠고

구현해내는 것도 머리 좀 쥐어짰던 문제였다. 디버깅에도 시간이 굉장히 걸린문제였다.