[백준] 드래곤 커브 JAVA
저번주 금요일에 풀었던 문젠데, 올리는 걸 깜빡했다.
잘 모르겠어서 검색해보고 다른 사람들 컨셉을 확인 후에 풀어봤는데 그래도 오래걸렸다.
연습이 매우 필요한 시점.. 시뮬레이션 문제는 신경써야할 게 많아서 은근히 어렵다.
커브를 만드는 것이 관건인 문제이다.
정사각형은 커브를 만든 후에 맵 전체를 확인해보면 된다.
공식을 사용해서 돌리는 경우도 있었는데, 수학을 다시 생각하자니 뭔가 그래서 다른 방법을 사용했다.
풀이
커브를 그리기 전에 먼저 커브가 찍히는 방향을 저장하고, 그 방향으로 전진하도록 작성했다.
예를 들어서 예제였던 (3,3)의 0방향을 시작으로 다음 세대의 방향을 생각해보면 아래와 같다.
| 0세대 | 1세대 | 2세대 | 3세대 | 4세대 |
| 0 | 1 | 2 1 | 2 3 2 1 | 2 3 0 3 2 3 2 1 |
숫자로 확인해 보면 방향의 규칙이 살짝 보인다.
이전 세대의 가장 끝 방향부터 차례대로 왼쪽으로 돌리는 것을 확인할 수 있다.
(0~1세대: 0121 > 2세대: 2321)
이를 통해 왼쪽으로 돌리는 것의 규칙이 (이전 방향 + 1) % 4인 것도 알 수 있다.
가장 끝 방향이 다음 세대의 처음이 되기 때문에 Stack에 세대 정보를 저장하고 다음 세대를 만들었다.
Stack을 하나로만 사용하면 새로운 세대 정보를 저장하는데 어려움이 있기 때문에,
세 개의 Stack과 하나의 Queue를 사용했다.
세대의 전체 정보를 저장하는 fullStack과 이전 세대 정보를 저장할 oldStack, 새로운 세대의 정보를 저장할 newQueue로 방향 정보를 저장하고
드래곤 커브를 그리기 위해서는 최초 방향이 먼저 나와야하기 때문에 fullStack에 저장된 정보를 newStack으로 새로 저장해 순서를 반대로 바꿔주었다.
커브를 만드는 것 외에도 주의해야할 사항이 있었는데 x,y의 정보가 배열 방식과는 반대로 주어지기 때문에 이 점을 주의해야한다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static int[][] curveInfo;
static int[][] map = new int[101][101];
static int[] nx = {0, 0, -1, 1};
static int[] ny = {1, -1, 0, 0};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int nDragonCurve = sc.nextInt();
curveInfo = new int[nDragonCurve][4];
for(int i = 0; i < nDragonCurve; i++) {
for(int j = 0; j < 4; j++) {
curveInfo[i][j] = sc.nextInt();
}
}
CreateCurve();
System.out.println(cntSquare());
}
public static void CreateCurve() {
Stack<Integer> fullStack = new Stack<>();
Stack<Integer> oldStack = new Stack<>();
Queue<Integer> newQueue = new LinkedList();
for(int i = 0; i < curveInfo.length; i++) {
int[] location = new int[2];
location[1] = curveInfo[i][0]; //x
location[0] = curveInfo[i][1]; //y
map[location[0]][location[1]] = 1;
int nDirection = curveInfo[i][2];
fullStack.push(nDirection);
for(int j = 0; j < curveInfo[i][3]; j++) {
while(!(fullStack.isEmpty())) {
nDirection = fullStack.pop();
oldStack.push(nDirection);
nDirection = (nDirection + 1) % 4;
newQueue.offer(nDirection);
if(fullStack.isEmpty()) {
while(!(oldStack.isEmpty())) {
fullStack.push(oldStack.pop());
}
while(!(newQueue.isEmpty())) {
fullStack.push(newQueue.poll());
}
break;
}
}
}
Stack<Integer> newStack = new Stack<>();
while(!(fullStack.isEmpty())) {
newStack.push(fullStack.pop());
}
while(!(newStack.isEmpty())) {
nDirection = newStack.pop();
nextLine(location, nDirection);
map[location[0]][location[1]] = 1;
}
}
}
public static void nextLine(int[] location, int nDirection) {
switch(nDirection) {
case 0:
location[1] += 1;
break;
case 1:
location[0] -= 1;
break;
case 2:
location[1] -= 1;
break;
case 3:
location[0] += 1;
break;
}
}
public static int cntSquare() {
int nCnt = 0;
for(int i = 0; i < 100; i++) {
for(int j = 0; j < 100; j++) {
if(map[i][j] == 1 && map[i+1][j] == 1 && map[i][j+1] == 1&& map[i+1][j+1] == 1)
nCnt++;
}
}
return nCnt;
}
}