15658 드래곤 커브 : https://www.acmicpc.net/problem/15685
Problems
Solves
처음에 문제를 이해를 못해서 많은 시간이 걸렸다. 드래곤 커브가 무조건 하나로 연결이 되어 있어야 한다고 이해를 하고 봤기 때문에 "1세대 드래곤 커브가 연결이 안되어있는데 어떻게 다음 세대 드래곤 커브가 기준을 잡고 연결을 하지?"라는 생각을 하면서 힌트를 보아도 여전히 이해를 하지 못했었다.. 드래곤 커브는 무조건 연결되어 있는 것이 아니라 각 다른 드래곤 커브들이 존재하는데 이때 모든 드래곤 커브들이 지나는 꼭짓점을 가지는 사각형의 갯수라는 것을 이해하고 어떻게할지 생각해보았다.
서론이 길었다. 처음엔 각 시작 좌표에서 주어진 방향으로 이리 저리 이동시켜보니 규칙을 찾아내었다.
예를 들어 0세대 드래곤 커브의 (0,0)에서 0의 방향(→)으로 이동하게 되면 (1,0)을 기준으로 시계방향으로 90도 회전한 결과가 다음세대 드래곤 커브라고 하였다. 그렇게 되면 1세대 드래곤 커브의 방향은 1 방향(↑)이 추가 [0,1]이 된다.
1번의 예시를 따라 가보면
0세대 : →(0)
1세대 : →(0) ↑(1)
2세대 : →(0) ↑(1) ←(2) ↑(1)
3세대 : →(0) ↑(1) ←(2) ↑(1) ←(2) ↓(3) ←(2) ↑(1)
...
이 순서대로 이전 세대의 방향이 뒤에서 부터 +1 씩 증가한 방향이 되고 3은 0 방향이 된다.
즉 (d+1)%4 의 식을 이용하면 된다.
그렇다면 구현해야하는 것은 주어진 N개의 드래곤 커브의 각 세대 만큼 방향을 생성하고, 그 방향으로 이동하면서 방문한 꼭짓점 방문 여부를 확인하면 몇개의 사각형의 꼭짓점이 드래곤 커브의 일부인지를 확인할수 있다.
Code
public class 드래곤커브 {
static boolean[][] map = new boolean[101][101];
static List<Integer>[] listOfGeneral;
static Point[] generals;
static int N;
static int[] dy = {0, -1, 0, 1};
static int[] dx = {1, 0, -1, 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));
N = Integer.parseInt(br.readLine());
//각 드래곤커브의 방향을 저장
listOfGeneral = new ArrayList[N];
//각 드래곤커브의 정보를 저장
generals = new Point[N];
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());
generals[i] = new Point(x, y, g);
listOfGeneral[i] = new ArrayList<>();
listOfGeneral[i].add(d);
map[y][x] = true;
int ny = y+dy[d];
int nx = x+dx[d];
//해당 드래곤커브의 시작 점에서 방향으로 이동한 좌표로 변경
generals[i].y = ny;
generals[i].x = nx;
//해당 좌표에 드래곤커브의 일부임을 표시
map[ny][nx] = true;
}
//주어진 각 드래곤 커브
for (int i = 0; i < N; i++) {
//해당 드래곤 커브를 주어진 세대까지 방향을 생성
//주어진 세대까지 이전 세대의 방향의 가지고 해당 세대의 방향을 생성
for (int j = 0; j < generals[i].general; j++) {
//새로운 방향이 listOfGeneral[i]에 저장되어도 길이를 고정시키기 위한 변수
int size = listOfGeneral[i].size()-1;
//이전 세대의 방향을 뒤에서 부터 +1씩 변경시켜준다.
for (int d = size; d >= 0; d--) {
int nd = (listOfGeneral[i].get(d) + 1) % 4;
int ny = generals[i].y + dy[nd];
int nx = generals[i].x + dx[nd];
if (ny < 0 || nx < 0 || nx > 100 || ny > 100)
continue;
generals[i].y = ny;
generals[i].x = nx;
//해당 좌표가 드래곤 커브의 일부임을 표시
map[generals[i].y][generals[i].x] = true;
//새로 생성된 방향이 저장
//새로운 방향이 저장되므로 size를 통해 이전 세대 방향의 크기를 고정시켜줌
listOfGeneral[i].add(nd);
}
}
}
int count = 0;
//좌표를 최대 (99,99)까지만 탐색하여 기준 꼭짓점으로 부터 4개의 꼭짓점이 모두 방문되어있다면 조건을 만족하는 사각형이므로 count++
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++;
}
}
}
bw.write(String.valueOf(count));
bw.flush();
bw.close();
}
static class Point {
int x;
int y;
int general;
public Point(int x, int y, int general) {
this.x = x;
this.y = y;
this.general = general;
}
}
}Result
