문제

BOJ 15685, 드래곤 커브

핵심

• 입력의 크기가 $100, 100, 2^{10}(세대)$이라 구현에 초점을 맞춘다.
  
• 드래곤 커브에 속하는 1 x 1 정사각형 개수를 구하는 문제이다. 드래곤 커브의 규칙성을 찾아내는 것이 핵심이다.
• 세대가 업할수록 기존 세대를 시계방향으로 90도 회전시킨 뒤 붙이는 작업을 반복한다. 이 문제는 해당 규칙을 찾으면 쉽게 풀 수 있다. 물론 규칙 찾기는 어렵다.
  • 0세대일 때 [0, 0][1, 0] 을 지난다.
  • 1세대일 때 기존 좌표 + [1, -1]을 지난다.
  • 2세대일 때 기존 좌표 + [0, -1], [0, -2]을 지난다.
  • 3세대일 때 기존 좌표 + [-1, -2], [1, -1], [-2, -1], [-2, -2]을 지난다.
  • 이를 다시 방향 관점에서 살펴보면
  • 시작점에서 방향 [0] 으로 0세대를 만들 수 있다.
  • 시작점에서 방향 [0, 1] 으로 1세대를 만들 수 있다.
  • 시작점에서 방향 [0, 1, 2, 1] 으로 2세대를 만들 수 있다.
  • 시작점에서 방향 [0, 1, 2, 1, 2, 3, 2, 1] 으로 3세대를 만들 수 있다.
  • 즉 기존 방향에서 뒤엣것부터 +1 하여 방향에 추가하면 규칙을 찾을 수 있다.
• 배열을 뒤의 원소부터 + 1을 더하여 다시 삽입하는 방식으로 세대 수만큼 반복하면 구할 수 있다. 코드로 표현하면 다음과 같다.

while (g--) {
	int vSize = dir.size();
	for (int i = vSize - 1; i >= 0; --i)
		dir.push_back((dir[i] + 1) % 4);
}

• 해당 수열을 구했으면 드래곤 커브로 둘러싸인 정사각형의 개수를 구하기 위해 시작점부터 방향을 더해가면서 grid 배열에 방문 표시를 한다. grid 배열에 [i, j], [i+1, j], [i, j+1], [i+1,j+1] 방문했다면 드래곤 커브에 쌓인 정사각형에 해당한다.

개선

코드

시간복잡도

• $O(n \times 2^g)$

C++

#include <iostream>
#include <vector>
using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int n;
int grid[104][104];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);	
	cin >> n;
	vector<int> dir;
	while (n--) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		dir.push_back(d);
		while (g--) {
			int vSize = dir.size();
			for (int i = vSize - 1; i >= 0; --i)
				dir.push_back((dir[i] + 1) % 4);
		}
		grid[y][x] = 1;
		for (int i = 0; i < (int)dir.size(); ++i) {
			x += dx[dir[i]];
			y += dy[dir[i]];
			grid[y][x] = 1;
		}
		dir.clear();
	}
	int ans = 0;
	for (int i = 0; i < 101; ++i) {
		for (int j = 0; j < 101; ++j) {
			if (grid[i][j] == 1 && grid[i][j + 1] == 1 
            	&& grid[i + 1][j] == 1 && grid[i + 1][j + 1] == 1)
				++ans;
		}
	}
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int[][] grid = new int[104][104];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> dir = new ArrayList<>();
        while (n-- > 0) {
            StringTokenizer 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());
            dir.add(d);
            while (g-- > 0) {
                int dirSize = dir.size();
                for (int i = dirSize - 1; i >= 0; --i)
                    dir.add((dir.get(i) + 1) % 4);
            }
            grid[y][x] = 1;
            for (int i = 0; i < dir.size(); ++i) {
                x += dx[dir.get(i)];
                y += dy[dir.get(i)];
                grid[y][x] = 1;
            }
            dir.clear();
        }
        int ans = 0;
        for (int i = 0; i < 101; ++i) {
            for (int j = 0; j < 101; ++j) {
                if (grid[i][j] == 1 && grid[i][j + 1] == 1 
                	&& grid[i + 1][j] == 1 && grid[i + 1][j + 1] == 1)
                    ++ans;
            }
        }
        System.out.println(ans);
        br.close();
    }
}