BOJ 15685
위 문제는 백준 사이트의 알고리즘 15685 문제에 관한 설명입니다.
문제
드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다.
좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.
- 시작 점
- 시작 방향
- 세대
0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다.
아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.
1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로
시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다.
끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.
2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)
3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.
즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음,
그것을 끝 점에 붙인 것이다.
크기가 100×100인 격자 위에 드래곤 커브가 N개 있다.
이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인
정사각형의 개수를 구하는 프로그램을 작성하시오.
격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.
입력
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다.
드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다.
x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)
입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다.
드래곤 커브는 서로 겹칠 수 있다.
방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.
- 0: x좌표가 증가하는 방향 (→)
- 1: y좌표가 감소하는 방향 (↑)
- 2: x좌표가 감소하는 방향 (←)
- 3: y좌표가 증가하는 방향 (↓)
출력
첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.
package 삼성기출;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ15685드래곤커브 {
static int N;
static int x;
static int y;
static int d;
static int g;
static int[] dx = { 1, 0, -1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static boolean[][] map = new boolean[101][101];
static List<Integer> directions;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
DragonCurve();
}
int count = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])
count++;
}
}
System.out.println(count);
}
static void DragonCurve() {
directions = new ArrayList<>();
directions.add(d);
int dir;
for (int i = 0; i < g; i++) {
for (int j = directions.size() - 1; j >= 0; j--) {
dir = (directions.get(j) + 1) % 4;
directions.add(dir);
}
}
int currentX = x;
int currentY = y;
map[x][y] = true;
for (int i = 0; i < directions.size(); i++) {
dir = directions.get(i);
int nextX = currentX + dx[dir];
int nextY = currentY + dy[dir];
map[nextX][nextY] = true;
currentX = nextX;
currentY = nextY;
}
}
}
이번 문제는 시뮬레이션 문제입니다.
부분을 나눠서 설명해보겠습니다.
입력부
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
DragonCurve();
}
각각의 입력값을 받는것을 N번 실행합니다.
이후 DragonCurve 메소드를 실행합니다.
DragonCurve()
static void DragonCurve() {
directions = new ArrayList<>();
directions.add(d);
int dir;
for (int i = 0; i < g; i++) {
for (int j = directions.size() - 1; j >= 0; j--) {
dir = (directions.get(j) + 1) % 4;
directions.add(dir);
}
}
int currentX = x;
int currentY = y;
map[x][y] = true;
for (int i = 0; i < directions.size(); i++) {
dir = directions.get(i);
int nextX = currentX + dx[dir];
int nextY = currentY + dy[dir];
map[nextX][nextY] = true;
currentX = nextX;
currentY = nextY;
}
}
드래곤 커브가 그려지기 위해서 directions에는 방향에 대한 값이 들어갑니다.
처음 설정된 방향인 d가 추가 되고나서
g라는 세대의 횟수만큼 반복문을 실행합니다.
내부에 있는 j는 모든 세대에 대해서 영향을 받음과 동시에
예시에서처럼 생각하면 Stack 처럼 쌓이는 형식입니다.
따라서 뒤에서 부터 하나씩 꺼내왔습니다.
이제 내가 있는 위치에 대해서 map에 방문처리(true) 해줍니다.
그리고 다음에 이동할 위치에 대해서 방문처리하고 이동해줍니다.
계산 및 출력부
int count = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])
count++;
}
}
System.out.println(count);
모든 맵에 대해서 한 좌표씩 살펴봅니다.
기준이 되는 좌표는 사각형의 좌상지점이고,
여기서 1칸씩 확인을 해봤을 때 사각형이 나온다면
사각형의 갯수를 늘려줍니다.
그리고 전부 확인을 했다면 사각형의 갯수를 출력합니다.