[JAVA] BOJ 백준 15685 - 건강한 생활

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

15685호:드래곤 커브

연 곡선의 수 N(1 ≤ N ≤ 20)은 첫 번째 줄에 표시됩니다.

연 곡선 정보는 두 번째 행부터 N행까지 제공됩니다.

카이트 커브 정보는 4개의 정수 x, y, d, g로 구성됩니다.

x와 y는 드래곤 코어입니다.

'추천 관련글,

www.acmicpc.net

이 문제에서 한 가지 주의할 점은 정사각형의 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;
	}
}

우리는 노드를 통해 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을 넘지 않기 때문에 포인트 배열은 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에서 연곡선의 수를 받아 연곡선 정보를 받아 point에 저장하고 연곡선을 그리는 함수를 호출한다.

그런 다음 함수 호출이 완료되면 점에서 점으로 점을 그립니다.

그런 다음 다음 드래곤 커브로 이동해야 합니다.

sx,sy 배열은 연곡선으로 진입하는 사각형을 조사할 때 사용되며, 점을 기준으로 현재 위치, 오른쪽, 아래, 오른쪽 아래 대각선 방향을 검색할 수 있습니다.

	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를 사용하여 다음 점을 검사하므로 4방향 모두에 점이 있어야 결과에 도달합니다.

결과를 출력

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;
	}

드래곤 기능은 0세대와 나머지로 나뉩니다.

이때 0세대의 경우 시작점과 시작점에 가장 가까운 지점을 점으로 설정한다.

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

재귀적으로 호출하여 이전 세대를 그립니다.
ArrayDeque를 선언하여 끝점을 가져오고 추가할 점을 채웁니다.
점에 있는 점을 살펴보고 90도 회전한 점을 추가하여 추가합니다.

(그릴 때 90도 회전한 점을 찾는 방법을 생각해보자!
)
끝점에서 Add에 점을 붙여넣기!
(그래서 다음 세대가 종점을 쉽게 선택할 수 있습니다!
)

add에서 마지막 포인트를 얻는 것은 별 의미가 없습니다… 그럴 필요는 없습니다.