[JAVA] BOJ 백준 15685 드래곤 커브

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

15685번: 드래곤 커브

이 문제에서 조심해야할 부분은 정사각형의 4 꼭지점이 모두 드래곤 커브에 들어오게 되면 (즉, 모두 선으로 연결된 점들 중 하나이면) 개수를 세어줘야 한다는 것이다.

나는 이 문제를 생성된 점을 모두 dot이라는 ArrayDeque에 넣어 관리한 다음 모든 점이 생성된 후 점을 그려주는 방식으로 해결하였다! (사실 문제 푸는데 조언을 좀 얻었다…)

이때 중요하게 생각해야할 부분은 직선이 그어지는 순서대로 점들을 저장해야 한다는 것이다.

예를 들어

이 문제에서 조심해야할 부분은 정사각형의 4 꼭지점이 모두 드래곤 커브에 들어오게 되면 (즉, 모두 선으로 연결된 점들 중 하나이면) 개수를 세어줘야 한다는 것이다.

나는 이 문제를 생성된 점을 모두 dot이라는 ArrayDeque에 넣어 관리한 다음 모든 점이 생성된 후 점을 그려주는 방식으로 해결하였다! (사실 문제 푸는데 조언을 좀 얻었다…)

이때 중요하게 생각해야할 부분은 직선이 그어지는 순서대로 점들을 저장해야 한다는 것이다.

예를 들어

이 경우 (0, 0) → (1, 0) → (1, -1)의 순서로 저장해야 한다.

전체 코드

import java.util.*;
import java.io.*;

class Node{
	public int x;
	public int y;
	public int d;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public Node(int x, int y, int d) {
		this(x, y);
		this.d = d;
	}
}
public class Main {
	static int dx[] = {0, -1, 0, 1};
	static int dy[] = {1, 0, -1, 0};
	static int dots[][] = new int[101][101];
	static ArrayDeque<Node> dot;
	static int result;
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(bf.readLine());
		int sx[] = {0, 1, 0, 1};
		int sy[] = {0, 0, 1, 1};
		for(int t=0; t<T; t++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			dot = new ArrayDeque<>();
			dragon(Integer.parseInt(st.nextToken()), new Node(y, x, d));
			while(!dot.isEmpty()) {
				Node s = dot.poll();
				dots[s.x][s.y] = 1;
			}
		}
		for(int i= 0; i< 100; i++) {
			f: for(int j=0; j< 100; j++) {
				for(int d= 0; d<4; d++) {
					int nx = i+sx[d]; int ny = j+sy[d];
					if(dots[nx][ny] != 1) continue f;
				}
				result++;
			}
		}
		System.out.println(result);
	}
	
	static void dragon(int gene, Node node){
		if(gene == 0) {
			int nx = node.x + dx[node.d];
			int ny = node.y + dy[node.d];
			dot.add(node);
			dot.add(new Node(nx, ny));
			return;
		}
		dragon(gene-1, node);
		Node n = dot.getLast();
		ArrayDeque<Node> add = new ArrayDeque<>();
		for(Node d : dot) {
			if(d.x == n.x && d.y == n.y) continue;
			int tempx = d.x - n.x;
			int tempy = d.y - n.y;
			add.add(new Node(n.x + tempy, n.y - tempx));
		}
		n = add.getLast();
		while(! add.isEmpty()) {
			Node temp = add.pollLast();
			dot.add(temp);
		}
	}
}

한 줄 씩 살펴보자!

class Node{
	public int x;
	public int y;
	public int d;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public Node(int x, int y, int d) {
		this(x, y);
		this.d = d;
	}
}

node를 통해 점들과 1세대 드래곤 커브를 관리할 것이다. 그렇기 때문에 생성자를 두 부류로 생성해준다.

static int dx[] = {0, -1, 0, 1};
static int dy[] = {1, 0, -1, 0};
static int dots[][] = new int[101][101];
static ArrayDeque<Node> dot;
static int result;

드래곤 커브는 0~100을 벗어나지 않기 때문에 dots 배열은 101로 선언한다. (문제를 읽어보면 0~100의 점을 모두 사용하기 때문)

result 변수에 결과값을 저장해준다.

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(bf.readLine());
int sx[] = {0, 1, 0, 1};
int sy[] = {0, 0, 1, 1};
for(int t=0; t<T; t++) {
	StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
	int x = Integer.parseInt(st.nextToken());
	int y = Integer.parseInt(st.nextToken());
	int d = Integer.parseInt(st.nextToken());
	dot = new ArrayDeque<>();
	dragon(Integer.parseInt(st.nextToken()), new Node(y, x, d));
	while(!dot.isEmpty()) {
		Node s = dot.poll();
		dots[s.x][s.y] = 1;
	}
}

T에 드래곤 커브의 개수를 받아주고 드래곤 커브 정보들을 받아 dot에 저장한 뒤 드래곤 커브를 그려주는 함수를 호출한다.

그 뒤 함수 호출이 종료되면 dot의 점들을 이용하여 점을 그려준다.

그리고 다음 드래곤 커브로 넘어가야 한다.

sx, sy 배열은 드래곤 커브에 들어가는 정사각형을 조사할 때 사용할 것으로 하나의 점을 기준으로 현재 위치, 오른쪽, 아래, 오른쪽 아래 대각선 4 방향을 탐색할 수 있도록 하였다.

	for(int i= 0; i< 100; i++) {
		f: for(int j=0; j< 100; j++) {
			for(int d= 0; d<4; d++) {
				int nx = i+sx[d]; int ny = j+sy[d];
				if(dots[nx][ny] != 1) continue f;
			}
			result++;
		}
	}
	System.out.println(result);
}

이중 for문을 통해 점들을 탐색한다. 이때 4 방향의 점중 어떤 방향이라도 점이 존재하지 않는 경우 continue를 이용하여 다음 점을 조사하기 때문에 result에 닿는 것은 4방향에 모두 점이 존재할 때 뿐이다.

result를 출력한다.

static void dragon(int gene, Node node){
	if(gene == 0) {
		int nx = node.x + dx[node.d];
		int ny = node.y + dy[node.d];
		dot.add(node);
		dot.add(new Node(nx, ny));
		return;
	}

dragon 함수는 0세대와 그 나머지 세대로 나뉜다. 이때 0세대의 경우는 시작점과 시작점의 방향으로 다음 점을 dot에 넣어준다.

0세대를 제외한 다른 세대들은 직전 세대와 직전 세대가 90도 회전한 모양을 끝점끼리 연결한 것이다. 그렇기 때문에 직전 세대와 90도 회전한 모양으로 나눌수 있다. 직전 세대는 재귀를 이용하여 받아오고 90도 회전한 모양은 “끝점을 기준으로” 90도 회전한 점들을 넣어주는 방식을 이용했다.

결국 그려주는 것은 0세대 뿐인 것이다!

코드를 마저 보겠다.

		dragon(gene-1, node);
		Node n = dot.getLast();
		ArrayDeque<Node> add = new ArrayDeque<>();
		for(Node d : dot) {
			if(d.x == n.x && d.y == n.y) continue;
			int tempx = d.x - n.x;
			int tempy = d.y - n.y;
			add.add(new Node(n.x + tempy, n.y - tempx));
		}
		n = add.getLast();
		while(! add.isEmpty()) {
			Node temp = add.pollLast();
			dot.add(temp);
		}
	}
}

0세대가 아닌 경우

1. 재귀 호출해 직전 세대를 그려준다.
2. 끝점을 받아와서 추가될 점들을 넣어줄 ArrayDeque을 선언한다.
3. dot에 있는 점들을 조사하여 90도 회전한 점들을 add에 넣어준다. (이것은 직접 그려보면서 어떻게 90도 회전한 점을 구할지 고민해보자!)
4. add에 있는 점들을 끝점부터 넣어준다! ( 다음 세대에서 편하게 끝점을 뽑을수 있도록!)

add에서 마지막 점을 가져온 것은 별 의미 없다.. 없어도 된다.