[백준 / BOJ] 1030 프렉탈 평면 (Java)

문제

출처 : https://www.acmicpc.net/problem/1030

1030번: 프렉탈 평면

7개의 정수 s, N, K, R1, R2, C1, C2 가 주어진다.

1*1그리드는 매 초마다 N*N그리드로 나뉘어지며 이때, 나뉜 정사각형이 흰색이라면, 가운데 K*K칸이 검은색으로 변한다. s초가 지났을때, R1,C1에서 R2,C2그리드를 출력하는 문제다.

 

---

풀이

수학?과 분할정복으로 푸는 문제였다.

 

문제를 풀기위해 우선, N*N 그리드가 매초마다 K*K조각으로 나누어질때, s초가 지난후 위치하는 좌표를 구해야한다.

예를들어,

1*1그리드가 매 초마다 3*3의 조각으로 나뉠때, 2초가 지난후 각 그리드의 위치를 구해보면,

1초 - 1*1그리드가 3*3으로 나뉘어진다. 이때, 9등분된 그리드의 (최종적으로 도달할)위치를 표시하면 다음과 같다.

(0,0) (0,3) (0,6)

(3,0) (3,3) (3,6)

(6,0) (6,3) (6,6)

 

이런식으로 다음 그리드의 위치를 계산해서 저장해줘야한다.

 

계산하는식은 다음과 같이 구할수있다.

 

1. 매 초 마다 N만큼 그리드가 나뉘어지므로, s초가 지난후 그리드의 칸수는 N^s이다.

2. 1번을 토대로, s초가 지났을때, 현재 칸이 N으로 나뉘어진다면, 다음칸의 위치는 다음과 같이 구할수있다.

-> (y + (totalGrid / (N*(s+1))) * nextY, x + (totalGrid / (N*(s+1))) * nextX)

nextY와 nextX는 다음 칸의 위치이다. (0..N-1)

totalGrid는 s초가 지난후 그리드의 칸 수 이다. (N^s)

 

재귀로 구현한 식을 한줄로 쓴거라 위 식이 틀릴수도 있다. (저런 느낌으로 구현할것을 생각하며 아래 코드를 보자.)

    private void setArr(int sec, long y, long x, long grid, int fill){
        if(y > R2 || x > C2) return;
        if(y + grid <= R1 || x + grid <= C1) return;
        if(sec == S) {
            arr[(int)(y-R1)][(int)(x-C1)] = fill;
            return;
        }
        long gridDivN = grid / N;
        long fillLeft = (N-K)/2;
        long fillRight = fillLeft+K-1;
        for(int i = 0; i < N; i++){
            long nextY = y + gridDivN * i;
            for(int j = 0; j < N; j++){
                long nextX = x + gridDivN * j;
                int nextFill = fill;
                if(nextFill == 0 && i >= fillLeft && i <= fillRight && j >= fillLeft && j <= fillRight) nextFill = 1;
                setArr(sec+1, nextY, nextX, gridDivN, nextFill);
            }
        }
    }

 

이런식으로 분할정복을 수행하며, 최종결과를 출력하면 답이나온다.

시간초과를 피하기위해 필요없는 부분은 안 봐줘야 한다.  (2^30*2^30개의 그리드가 나올수있으므로, 최적화를 하지않는다면 2^30*2^30 번 반복한다.)

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1030%20%ED%94%84%EB%A0%89%ED%83%88%20%ED%8F%89%EB%A9%B4/Main.java

devxb/JJUNalgo