문제
100 x 100 격자 위에 N개의 드래곤 커브를 그린 후, 네 꼭짓점이 모두 드래곤 커브에 포함된 1 x 1 정사각형의 개수를 구하라.
입력
첫째 줄에 드래곤 커브 수 N (1 ≤ N ≤ 20), 이후 N줄에 시작점 (x, y), 시작 방향 d, 세대 g가 주어진다. 방향: 0(우), 1(상), 2(좌), 3(하).
출력
네 꼭짓점이 모두 드래곤 커브에 포함된 1 x 1 정사각형의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 3 0 1 4 2 1 3 4 2 2 1 | 4 |
풀이
드래곤 커브의 방향 리스트를 세대별로 확장한 후 격자에 표시하고, 1 x 1 정사각형을 카운트한다.
- 0세대는 시작 방향 하나로 구성된 방향 리스트를 만든다
- 다음 세대는 이전 방향 리스트를 역순으로 순회하며 각 방향에 +1(90도 회전)한 값을 뒤에 추가한다
- g세대까지 확장 후, 시작점에서 방향 리스트를 따라 이동하며 지나는 좌표를 boolean 배열에 표시한다
- 100 x 100 격자를 순회하며 (i,j), (i+1,j), (i,j+1), (i+1,j+1) 모두 true인 정사각형을 센다
핵심 아이디어: k세대 드래곤 커브는 (k-1)세대를 끝점 기준으로 90도 회전한 것을 이어붙인 형태이므로, 방향 리스트를 역순+90도로 복제하면 된다.
코드
package ASP_study.day299;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day292BOJ15685드래곤커브 {
static boolean[][] map = new boolean[101][101];
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, -1, 0, 1};
static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
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()); // 세대
dragonCurve(x, y, d, g);
}
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
ans++;
}
}
}
bw.write(ans + "\n");
br.close();
bw.flush();
bw.close();
}
public static void dragonCurve(int x, int y, int d, int g) {
List<Integer> d_list = new ArrayList<>();
d_list.add(d);
for (int i = 1; i <= g; i++) {
for (int j = d_list.size() - 1; j >= 0; j--) {
d_list.add((d_list.get(j) + 1) % 4);
}
}
map[y][x] = true;
for (Integer direction : d_list) {
x += dx[direction];
y += dy[direction];
map[y][x] = true;
}
}
}복잡도
- 시간: O(N * 2^g + 100²)
- 공간: O(2^g + 100²)