[백준] 드래곤 커브 (구현)

문제 : https://www.acmicpc.net/problem/15685

 

풀이과정

1. 드래곤 커브를 그리는 함수를 구현해야 합니다.

1-1. 리스트를 활용

드래곤 커브는 현재까지 만들어진 모양을 바탕으로 새로운 모양을 만들게 됩니다. 리스트를 활용해서 드래곤 커브의 방향을 구현했습니다.

 

1-2. 90도 회전

90도 회전의 경우

0 방향은 1

1 방향은 2

2 방향은 3

3 방향은 0

이 됩니다.

(현재방향+1)%4 연산을 통해 이를 구현할 수 있습니다.

 

static void update_history(){ // g번 이동시키기

        for(int i=0;i<g;i++){
            int size = history.size();
            for(int j=size-1;j>=0;j--){
                history.add((history.get(j)+1)%4);
            }
        }
    }

1-3. 두 번 이동 시키기

정사각형의 갯수를 구하기 위해 드래곤 커브를 그릴 때 한 번의 이동을 두 번의 이동으로 구현했습니다.

2칸 씩 이동하게 되면 드래곤 이동에 따른 빈 정사각형 칸을 구현할수 있기 때문입니다.

이를 위해서 배열의 크기를  문제의 조건인 (0 ≤ x ≤ 100, 0 ≤ y ≤ 100) *2배 크기로 초기화 했습니다.

시작점의 좌표 또한 2배 시켜줬습니다.

 

static void draw(){
        x*=2;
        y*=2;
        // 이때 배열에서 r행은 x좌표, c열은 y좌표
        arr[y][x] = 1;
        for(int i=0;i<history.size();i++){
            int d = history.get(i);
            for(int c=0;c<2;c++){ // 2칸씩 이동 시키기 (정사각형의 갯수를 구하기 위해서)
                x += dr[d];
                y += dc[d];
                arr[y][x] = 1;
            }
        }
    }

2. 정사각형의 갯수를 구해야 합니다.

드래곤 커브가 그려진 배열들을 완전탐색 하며 네 방향의 대각선에 1이 있는지 확인하며 갯수를 카운팅 합니다.

이때 정사각형이 있을 수 있는 좌표는 홀수 좌표입니다.

시작점의 x,y좌표 (1-3 과정에서 2배 시켜줌) 는 짝수이고, 이동하는 횟수도 짝수이기 때문입니다.

static int count(){
        int result = 0;

        for(int r=1;r<201;r+=2){ // 행과 열이 홀수인 칸에 대해서 탐색 (시작점은 무조건 짝수이고 짝수 갯수로 이동함)
            for(int c=1;c<201;c+=2){
                int cnt = 0;
                if(arr[r][c]!=0) continue; // 탐색하는 칸이 0이어야 함
                for(int d=0;d<4;d++){
                    int nr = r + ddr[d];
                    int nc = c + ddc[d];
                    if(nr<0 || nr>=201) continue;
                    if(nc<0 || nc>=201) continue;
                    if(arr[nr][nc]==0) break; // 하나라도 0이면 될 수 없음
                    if(arr[nr][nc]==1) cnt+=1;
                }
                if(cnt==4){
                    result+=1;
                }
            }
        }
        return result;
    }

 

출력과 같이 드래곤 커브를 그렸습니다.

 

알게된점

• 다른사람들의 풀이를 보니 직접 드래곤 커브를 그리지 않고, 꼭짓점에 대해서만 체크를 하여 구현할 수 있음을 알게되었습니다.
• 한 번의 이동을 두 번의 이동으로 보정하는 방식으로 문제를 해결할 수 있는 경우가 종종 있음을 느꼈습니다.

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;

// 1. 드래곤 커브 그리기
// - 이전 모양에 따라서 계속 새로운 모양이 만들어 짐
// - List를 스택으로 활용해서 현재 모양을 기반으로 계속 업데이트 하기
// - 이때 90도 회전했을 때 방향
// - 0 : 1
// - 1 : 2
// - 2 : 3
// - 3 : 0
// 2. 정사각형의 개수 구하기

public class Main {

    static int N;
    static int[] dr = {1,0,-1,0}; // 0, 1, 2, 3
    static int[] dc = {0,-1,0,1};
    static int[] ddr = {-1,-1,1,1};
    static int[] ddc = {-1,1,1,-1};
    static List<Integer> history;
    static int x,y,d,g;
    static int[][] arr;



    static void update_history(){ // g번 이동시키기

        for(int i=0;i<g;i++){
            int size = history.size();
            for(int j=size-1;j>=0;j--){
                history.add((history.get(j)+1)%4);
            }
        }
    }
    static void draw(){
        x*=2;
        y*=2;
        // 이때 배열에서 r행은 x좌표, c열은 y좌표
        arr[y][x] = 1;
        for(int i=0;i<history.size();i++){
            int d = history.get(i);
            for(int c=0;c<2;c++){ // 2칸씩 이동 시키기 (정사각형의 갯수를 구하기 위해서)
                x += dr[d];
                y += dc[d];
                arr[y][x] = 1;
            }
        }
    }

    static int count(){
        int result = 0;

        for(int r=1;r<201;r+=2){ // 행과 열이 홀수인 칸에 대해서 탐색 (시작점은 무조건 짝수이고 짝수 갯수로 이동함)
            for(int c=1;c<201;c+=2){
                int cnt = 0;
                if(arr[r][c]!=0) continue; // 탐색하는 칸이 0이어야 함
                for(int d=0;d<4;d++){
                    int nr = r + ddr[d];
                    int nc = c + ddc[d];
                    if(nr<0 || nr>=201) continue;
                    if(nc<0 || nc>=201) continue;
                    if(arr[nr][nc]==0) break; // 하나라도 0이면 될 수 없음
                    if(arr[nr][nc]==1) cnt+=1;
                }
                if(cnt==4){
                    result+=1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        N = Integer.parseInt(br.readLine());
        arr = new int[201][201];

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            history = new ArrayList<>(); // 이동방향 기록
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());
            history.add(d); // 시작방향 넣어줌
            update_history(); // g세대 만큼 이동했을 때 history를 업데이트
            draw(); // history로 그림 그려주기, 2칸 씩 이동시키기 (정사각형 꼭짓점 맛닿은 부분 계산하기 위해서)\

        }


        // 정사각형 갯수 카운트
        System.out.println(count());


    }
}