백준 15685번 : 드래곤 커브 [Java]

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

 

문제 탐색하기

문제에서는 드래곤 커브를 세대에 따라 좌표에 그려서 정사각형의 네 꼭짓점이 드래곤 커브가 모두 방문하는 지점을 찾으면 되는 문제이다. 문제의 요구사항이 세대별로 방향을 바꿔가며 그려야해서 복잡할 수 있지만 어떻게 그릴 수 있는지 생각해보자.

 

0세대일 때는 x나 y좌표로 한칸 이동하면 된다. 이제 1세대 부터 문제가 생기는데, 끝 점에서 이동하여서 0세대 드래곤 커브를 이동시켜서 끝점에 붙여야 한다. 이 말인 즉슨 이전 드래곤 커브를 어떻게 그렸는지 좌표를 기록해야한다. 여기서 좌표를 기록할 수도 있고 지나온 방향을 기록해도 괜찮다. 이번 풀이 방법에서는 방향을 기록하는 방식으로 구현했다. 

 

방향을 기록하는 방식으로 구현하려면 어떤 식으로 방향을 전환할 수 있을까. 문제 예시에서 확인해보면, 0세대의 그림에서 첫번째 시작점에서 첫번째 끝점으로 이동하는 방향 이후 세대에서도 방향이 계속 같다. 이에서 착안하여 다음세대의 그림을 그릴때는 이전의 끝점에서 지끝점까지 진행한 방향을 역순으로 거슬러 올라가되, 반대방향 (유턴) + 시계방향 90도 전환을 통해서 그림을 그릴 수 있다.

 

이를 좌표에 옮기기 위해서는 좌표에 모든 드래곤 커브에 대한 방문 체크를 하고 마지막에 모든 좌표를 확인해서 네 꼭짓점이 모두 방문 된것만 체크하여 답을 구할 수 있다.

 

코드 구현하기

1. 입력을 처리하고 방문 체크를 할 2차원 배열을 설정한다. 이 때 일부러 크게를 넉넉히 잡아서 영역 바깥으로 드래곤 커브가 나가지 않도록 구현하면 비교적 처리가 수월하다. 풀이에서는 x와 y좌표 제한을 일부러 1000정도로 크게 잡았다.
2. 각 드래곤 커브 모든 세대에서 아래 사항을 반복한다.
   1. 만약 현재 세대가 0일 경우 한방향만 기록하고 추가하여 방문체크를 해둔다.
   2. 현재 세대가 0이 아니라면 끝 점에서 기존 방향을 역순 + 방향 전환하여 방문하여 새로운 세대의 드래곤 커브를 만든다. 이때 이전 방문 기록에 현재 이동한 방향을 추가로 기록하여 이후 세대를 그릴때 사용한다.
3. 모든 드래곤 커브를 그렸다면 완전 탐색을 통해서 모든 좌표를 탐색하고 네 꼭짓점을 모두 방문한 정사각형들의 개수를 찾아서 출력한다.

풀이

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

public class Main {
	static int N, x, y;
	static boolean[][] visited = new boolean[1001][1001];
	static int[] dx = {0, -1, 0, 1};
	static int[] dy = {1, 0, -1, 0};
	static ArrayList<Node> curves = new ArrayList<>();

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		for (int i = 0; i < N; i++) {
			y = fr.nextInt() + 10;
			x = fr.nextInt() + 10;
			int d = fr.nextInt();
			int g = fr.nextInt();
			visited[x][y] = true;

			for (int j = 0; j < g + 1; j++) {
				if (j == 0) {
					x += dx[d];
					y += dy[d];
					visited[x][y] = true;
					curves.add(new Node(dx[d], dy[d], d));
				} else {
					addNextGen();
				}
			}
			curves.clear();
		}

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

	private static int check() {
		int result = 0;
		for (int i = 0; i < 1000; i++) {
			for (int j = 0; j < 1000; j++) {
				if (visited[i][j] && visited[i + 1][j] && visited[i][j + 1] && visited[i + 1][j + 1]) {
					result++;
				}
			}
		}
		return result;
	}

	private static void addNextGen() {
		ArrayList<Node> temp = new ArrayList<>();
		Collections.reverse(curves);
		for (Node n : curves) {
			int newDir = clockwise(uTurn(n.dir));
			x += dx[newDir];
			y += dy[newDir];
			visited[x][y] = true;
			temp.add(new Node(dx[newDir], dy[newDir], newDir));
		}
		Collections.reverse(curves);
		ArrayList<Node> next = new ArrayList<>();
		next.addAll(curves);
		next.addAll(temp);
		curves = next;
	}

	private static int uTurn(int i) {
		return (i + 2) % 4;
	}

	private static int clockwise(int i) {
		if (i - 1 == -1) {
			return 3;
		}
		return i - 1;
	}

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

	static class Node {
		int x, y, dir;

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