15685번: 드래곤 커브
첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커
www.acmicpc.net
0. N세대 드래곤 커브란? N-1세대 드래곤 커브를 끝 점 기준 90도 회전시켜 N-1세대의 끝 점에 붙인 것
- 한 세대마다 2배씩 증가하지만, 세대가 최대 10이므로 최대 pow(2,10), 1024개의 지점으로 구성된다
1. N세대 드래곤 커브를 만들기 위해선?
- N-1세대의 끝 점에서 시작해, N-1세대 커브의 구성을 역순으로 90도 회전시켜서 적용한다
- 예를들어, 위 2세대 커브는 →↑←↑ 순서로 이루어져 0, -2 지점에서 종료되었다.
- 3세대 커브를 만들려면 0, -2 지점에서 2세대 커브의 역순인 ↑←↑→ 이동을, 90도 회전시켜 ←↓←↑ 순서로 진행하면 된다
- 이는 문제 예시를 통해 확인 가능하다
2. 해당 과정을 위해 N세대까지 거쳐온 기록을 Arraylist로 저장하고, 이를 역순으로 탐색하며 끝점을 이동시킨다
3. 끝점은 분명한 경로를 가지고 움직이지만, 문제의 요구사항은 0<=x,y<=100 인 (x,y) 좌표에 대해서 정사각형을 구하는 것이므로, 끝 점이 방문한 좌표만 기록한다
4. 모든 커브가 그려진 후, 0~100의 좌표들에 대해서 사각형 조건 충족 여부를 검사, 출력한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main{
static int[][] dir= {
{0,1},
{-1,0},
{0,-1},
{1,0}
};
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cntSquare=0;
boolean[][] map = new boolean[101][101];
int N = pint(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int y = pint(st.nextToken());
int x = pint(st.nextToken());
int d = pint(st.nextToken());
int g = pint(st.nextToken());
if(inBox(x,y)) {
map[x][y]=true;
}
x+=dir[d][0];
y+=dir[d][1];
if(inBox(x,y)) {
map[x][y]=true;
}
//curve의 경로 저장
List<Integer>curve = new ArrayList<>();
curve.add(d);
for (int j = 0; j < g; j++) {
for (int j2 = curve.size()-1; j2 >= 0; j2--) {
//curve를 역순으로 탐색
int curDir = curve.get(j2);
//90도 회전
int nextDir=(curDir+1)%4;
//끝 점 이동 적용
x+=dir[nextDir][0];
y+=dir[nextDir][1];
if(inBox(x,y)) {
map[x][y]=true;
}
curve.add(nextDir);
}
}
}
//조건을 만족하는 사각형의 갯수 찾기
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]) {
cntSquare++;
}
}
}
System.out.println(cntSquare);
}
static boolean inBox(int x, int y) {
if(x>=0 && x<=100 && y>=0 && y<=100)return true;
return false;
}
static int pint(String s) {
return Integer.parseInt(s);
}
}