Baekjoon[15685] - 드래곤 커브

링크

15685번: 드래곤 커브

문제설명

• 시뮬레이션

문제풀이

• 세대에 걸쳐서 선을 긋고, 네 꼭지점에 선이 걸쳐있는 격자 칸의 개수를 구한다.

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main15685_드래곤커브 {

    public static int[][] dir = {
            {0,1},
            {-1,0},
            {0,-1},
            {1,0}
    };
    public static int[][] diodir = {
            {1,1},
            {1,-1},
            {-1,-1},
            {-1,1}
    };
    public static LinkedList<Integer>[] generation = new LinkedList[11];

    public static void main(String[] args) throws IOException {

//        generation array 생성
        for (int i = 0; i <= 10; i++) {
            generation[i] = new LinkedList<Integer>();
        }
        generation[0].add(0);

        for (int i = 1; i <= 10; i++) {
            LinkedList<Integer> temp = new LinkedList<Integer>();
            for (int g : generation[i-1]) {
                generation[i].add(g);
                temp.addFirst(((g+1)+4)%4);
            }
            for (int g : temp) {
                generation[i].add(g);
            }
        }

//        read
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int ans = 0;
        int N = Integer.parseInt(st.nextToken());
        int[][] input = new int[N][4];

//        짝수는 점, 홀수는 면    
        int[][] map = new int[201][201];

//        read
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 4; j++) {
                input[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
//            xy 좌표 생각
            int sr = input[i][1]*2;
            int sc = input[i][0]*2;
            map[sr][sc] = i+1;

            int nr = sr;
            int nc = sc;

            int rotate = input[i][2];
            int g = input[i][3];

            for (int move : generation[g]) {
                nr += dir[(move+rotate)%4][0];
                nc += dir[(move+rotate)%4][1];

//                선분 긋기
                map[nr][nc] = 1;

//                점 이동
                nr += dir[(move+rotate)%4][0];
                nc += dir[(move+rotate)%4][1];

//                점 찍기
                map[nr][nc] = i+1;
            }
        }




//        ans
        for (int i = 1; i <= 200; i=i+2) {
            for (int j = 1; j <= 200; j=j+2) {
//                4방탐색
                int cnt=0;
                int nr;
                int nc;
                for (int d = 0; d < 4; d++) {
                    nr = i + diodir[d][0];
                    nc = j + diodir[d][1];
                    if(map[nr][nc]>0) {
                        cnt++;
                    }
                }
                if(cnt==4) {
                    ans++;
                }
            }
        }


        System.out.println(ans);
    }
}

아쉬운 점

• 문제 잘못 읽었음
  • 격자 칸의 개수를 구하는 것을 덮어쓴 '선분'으로 생각했음.. 그래서 map[201][201]로 했었음
  • 격자 칸의 개수는 구하는 것은 4 꼭지점에 '선분'이 걸쳐있으면 됨 굳이 선분 안넣어도 됨. map[101][101]로 충분함.
  • dir설정 방향 반대로 착각했음

잘한 점

• 세대가 어떻게 퍼지는지 규칙성 찾아서 전역변수에 저장해놨음.
• 각 단계별 90도 회전하는걸 (+각도)%4 로 처리했음
• 0 방향에서의 0~10세대를 구한후에, 나머지 1,2,3 방향은 각각 1,2,3을 더해주는식으로 선분을 그렸음
• x,y 좌표 안헷갈림
• 1시간