백준 1030번 : 프렉탈 평면 자바

 

 

🧫 문제 분석

 

✔️ 출처

프렉탈 평면 골드 3

 

📖 문제

 

 

분할 정복 문제

증말 어려웠던 문제였다.

 

필자는 먼저 s초가 흐른 뒤의 크기부터 n으로 나눠가며 분할했다.

n^s → n ^s / n → n ^s - 1 / n ...

핵심

• black 체크 (어떻게 계속해서 분할되는 정사각형에서 black인지 아닌지 확인할 것인가)
• 주어진 범위를 벗어나면 탐색 범위 제외

 

black 체크

black 체크의 경우 

문제에서 나와있듯이 (N - K) % 2 = 0이다.

즉 , 분할한 각 구역의 시작 위치에서 대각선으로 (N - K) / 2 만큼 떨어져있다는 의미이기도 하다.

이를 블랙 포인트라 하자.

문제는 시간이 지날수록 n*n 씩 나눠지고, 사각형은 k*k 크기로 만들어진다. 

 

앞서 말했듯이 n^s 부터 시작한다. 

여기서 구한 블랙 포인트는 상대적이다. 

하나의 종이에서 n으로 나눴을 때 위치이다. 나는 n^s 에서 n으로 나누는 순으로 시작한다. 

n^s에서 n으로 나눴을 때 값을 div라 하자.

블랙포인트는 중앙에 있으므로 blackPoint * div 를 해주면 중앙 시작 위치를 얻게된다.

private static void recursion(int r, int c, int length, int second, boolean isBlack) {

    int div = length / n;

    int blackPoint = ((n - k) / 2) * div; 
    // 블랙 포인트 시작 위치 (r, c)
    int blackR = blackPoint + r;
    int blackC = blackPoint + c;
    
    //...
}

s = 2, N = 3, K = 1일 때

 1/N 로 봤을 때 상대적 블랙포인트가 대각선 화살표이고

1/N^2 가 N^s / n 을 한번 했을 때라고 보면 된다. 

 

설명하기 정말 어려운데 아무튼 저렇다.

직접 그림을 그려보고 코드로 짜보면 더 이해가 잘 될 것이라고 생각한다.

 

 

이제 div 만큼 이동하면서 각 구역을 재귀하여 탐색하는데

블랙은 k*k 크기로 만들어진다고 했다 .

따라서 k *div를 blackR , blackC에 더해준다. 

이유는 k만큼 생기는데 시간이 지날수록 div만큼 더 쪼개지기 때문..

// 중앙 블랙 처리 (블랙 범위 안에 있던지, 이전 분할 에서 해당 구역이 블랙이면 black
i >= blackR && j >= blackC && i < blackR + (k * div) && j < blackC + (k * div) || isBlack

 

 

 주어진 범위를 벗어나면 탐색 범위 제외

// 정해진 범위를 벗어낫 구역이면 넘기기
if ((r < r1 && r + length <= r1) || (c < c1 && c + length <= c1) || r > r2 || c > c2 ) return;

 

정말 정말 중요하다. 

우리는 출력할 크기와 위치를 받았기에 여기에 맞춰서 블랙을 넣어주어야한다.

 

가운데가 주어진 위치와 크기

 

이렇게 주어진 박스를 벗어나는 부분은 넘겨버리면 된다.

나오는 경우는 4가지이며

1. r < r1 && r + length <= r1
2. c < c1 && c + length <= c1
3. r > r2
4. c > c2

이렇게 볼 수 있다. 

r + length <= r1 에서 왜 < 가 아니냐면

배열에 블랙을 넣을 때 그냥 넣을 순 없다. 

배열은 0~r2까지, 0~c2까지이기에 여기에 맞춰서 넣어야한다.

따라서 r - r1, c -c1 을 해줘야한다. 

 length 가 1일 때 r1 화살표 바로 왼쪽 사각형을 생각해보자

 

r = 1이고 r +length = 2이다. r2 는 2이다. 

여기서 r + length < r1 을 해버리면

r - r1 에서 -1 로 arrayoutofboundsexception 에러가 터진다. 

따라서 r + length <= r1으로 뺏을 때 -1 이 되는 지 체크도 하게 된다고 생각하면 된다. 

 

 

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static int s, n, k, r1,r2,c1,c2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 원하는 위치의 그림 크기 초기화


        s = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        r1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        c1 = Integer.parseInt(st.nextToken());
        c2 = Integer.parseInt(st.nextToken());
        graph = new int[r2 - r1 + 1][c2 - c1 + 1];

        int size = (int) Math.pow(n, s);

        // n x n 으로 분할
        // k x k 정사각형으로 검은색이 채워짐
        // 가운데가 검정

        recursion(0, 0, size,0, false);

        System.out.println(27 / 2 );

        for (int[] ints : graph) {
            for (int n : ints) {
                sb.append(n);
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }


    private static void recursion(int r, int c, int length, int second, boolean isBlack) {

        // 정해진 범위를 벗어낫 구역이면 넘기기
        if ((r < r1 && r + length <= r1) || (c < c1 && c + length <= c1) || r > r2 || c > c2 ) return;

        // 크기가 1이고 블랙이면 1 처리
        if (length == 1 && isBlack) {
            graph[r -r1][c -c1] = 1;
            return;
        }


        int div = length / n;

        int blackPoint = ((n - k) / 2) * div;
        int blackR = blackPoint + r;
        int blackC = blackPoint + c;


        if (second < s) {
            for (int i = r; i < r + length; i += div) {
                for (int j = c; j < c + length; j += div) {

                    // 중앙 블랙 처리 (블랙 범위 안에 있던지, 이전 분할 에서 해당 구역이 블랙이면 black 
                    recursion(i, j, div, second + 1,  i >= blackR && j >= blackC && i < blackR + (k * div) && j < blackC + (k * div) || isBlack);

                }
            }
        }

    }


}

 

 

 

 

❗ 오답노트 / 필요한 지식

1.  설명하기 정말어렵다... 정말 생각할게 많은 문제였다. 잘 기억하자.