<Algorithm> 78. 15685번 드래곤커브

1. 15685번 드래곤커브

• 상반기 삼성전자 오후에 봤었던 문제이다. 당시에 손도 못댔고 지금도 접근법이 감이 안잡혀서 힌트를 보고 풀었다.

• 드래곤커브에 규칙이 있는데 방향을 누적하여 이전 세대까지 누적된 거에 역순으로 +1 씩 해주면 그 다음세대의 방향을 알 수 있었다.

• 처음에 점에 대한 규칙으로만 하려고 하니 점에 대한 규칙이 너무 복잡하고 계속 늘어나기 때문에 할 수가 없었다.

• 시뮬레이션으로 분류된 문제인데 이런 류의 문제는 여러 부분에 대한 규칙을 따져보아야 하는 것 같다.

• 특히 이렇게 누적되는 문제는 하나를 기준으로 하는 게 좋을 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static boolean[][] visited;
    static Stack<Integer> stack; 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st; 
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][4];
        visited = new boolean[300][300];
    
        for(int i = 0; i < N; i ++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 4; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i = 0; i < N; i++) {
            stack = new Stack<>();
            stack.add(arr[i][2]);
            init(arr, stack, arr[i][3], 0);
            visit(arr[i][0], arr[i][1]);
        }
        int res = 0;
        for(int i = 0; i < 300; i++) {
            for(int j = 0; j < 300; j++) {
                if(visited[i][j]) {
                    if(visited[i+1][j]&&visited[i][j+1]&&visited[i+1][j+1]) {
                        res++;
                    }
                }
            }
        }
        System.out.println(res);
    }
    
    public static void init(int[][] arr, Stack<Integer> stack, int g, int count) {
        
        if(count == g) return;            
        // 역순으로 이전에 누적된 값들을 +1씩해준다.
        for(int i = stack.size() -1; i >= 0; i--) {
            if(stack.get(i) != 3) {
                stack.add(stack.get(i)+1);
            }else {
                stack.add(0);
            }
        }
        
        init(arr, stack, g, count+1);
    }
    private static void visit(int x, int y) {
        x +=100;
        y +=100;
        visited[x][y] = true;
 
        for(int i = 0; i < stack.size(); i++){
            int order = stack.get(i); 
            // 드래곤커브 제작
            switch (order) {
                case 0 :
                    x++;
                    break;
                case 1 :
                    y--;
                    break;
                case 2 :
                    x--;
                    break;
                default:
                    y++;
                    break;
            }
            visited[x][y] = true;
        }
    }
}
 

참고 & 출처  http://limkydev.tistory.com/158