[백준] 별 찍기 - 10

프렉탈 구조

프랙탈은 자연에서 발견되는 복잡한 패턴을 수학적으로 모델링한 구조로, 재귀적인 자기 유사성을 특징으로 한다.

프랙탈은 간단한 규칙이 반복 적용되어 복잡하고 상세한 패턴이나 구조를 생성한다.

이러한 특성 때문에 프랙탈은 수학, 자연과학, 예술 등 다양한 분야에서 활용된다.

 

본 코드에서 구현된 프랙탈 별 패턴은 이러한 프랙탈의 개념을 바탕으로 한다.

각 단계마다 3x3 그리드를 기반으로 중앙을 비워두는 규칙을 재귀적으로 적용함으로써,

복잡하면서도 규칙적인 별 모양의 패턴을 생성한다.

 

이 패턴은 각 단계마다 하위 그리드로 나누어지며, 각 하위 그리드 내에서도 동일한 패턴이 반복되어 전체적인 프랙탈 구조를 형성한다.

 

 

프렉탈 구조

---

문제 설명

 

 

2차원 배열과 행을 x, 열을 y 로 생각해보면 된다.

 

N = 3 일 때만 생각해보자

2차원 배열이 선언되었다는 가정하에 ( arr[][] ) 인덱스는 0부터이므로 N = 3 일 때의 공백은 arr[1][1] 이다.

 

이 의미는 즉 행부터 채울 때, (0, 0), (0, 1), (0, 2), (1, 0) 까지는 별을 출력하고

별 출력이 4 번 이루어지면 그다음 블럭은 반드시 공백이라는 것이다.

 

먼저 N = 27 일 때 우리는 9개의 블록으로 구분할 수 있다.

위 수식에서 보았듯이 공백인 구간을 만족한다면 그 구간은 공백으로 채우고 공백 구간이 아닌 블럭은 재귀호출을 하면 된다.

 

그러면 N = 9 일 때로 넘어갈 것이다. 또 앞선 함수와 같이 9개의 블록으로 나눈 뒤,

공백 구간은 공백 문자로 채우고 공백이 아닌 구간을 다시 재귀 호출을 하는 것이다.

 

그렇게 된다면 N = 3 일 때로 갈 것이고, 위와 같은 과정을 반복하다 보면 결국 N = 1 일 때가 온다.

여기서는 더 못 쪼개기 때문에 해당 구역의 배열을 공백 또는 별(*) 로 채우면 되는 것이다.

 

---

코드 및 설명

public class Main {
    // 메인 메서드: N을 입력받고 별 패턴을 출력
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        printStars(N);
    }

    // isStar 메서드: 주어진 좌표 (x, y)에 별을 찍어야 하는지 결정
    private static boolean isStar(int x, int y, int N) {
        // N이 1일 때는 항상 별을 찍는다 (재귀 호출의 기본 케이스).
        if (N == 1) {
            return true;
        }
        // 가운데 공백인 경우 (중앙의 3x3 섹션).
        if (x / (N / 3) == 1 && y / (N / 3) == 1) {
            return false;
        }
        // 재귀 호출로 각 3x3 섹션을 확인
        return isStar(x % (N / 3), y % (N / 3), N / 3);
    }

    // printStars 메서드: N x N 그리드에 별 패턴을 출력
    private static void printStars(int N) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // isStar 메서드를 사용하여 해당 위치에 별을 찍을지 결정
                if (isStar(i, j, N)) {
                    sb.append("*");
                } else {
                    sb.append(" ");
                }
            }
            sb.append("\n");
        }
        // StringBuilder를 사용하여 문자열을 한 번에 출력
        System.out.print(sb.toString());
    }
}

 

1. 재귀 시작: isStar 메서드는 (x, y) 좌표와 그리드 크기 N을 받아 시작한다.
   
   
2. 기본 케이스: N == 1인 경우, 가장 작은 1x1 그리드에 해당하므로 항상 별을 찍어야 한다.
   
   
3. 중앙 공백 판단: x / (N / 3)과 y / (N / 3) 계산으로 현재 좌표가 중앙 3x3 섹션인지 확인한다. 중앙 섹션에 해당하면 공백으로 처리해야 하므로 false를 반환한다.
   
   
4. 재귀 호출로 하위 그리드 판단: x % (N / 3)과 y % (N / 3) 연산은 좌표를 하위 3x3 섹션 내의 상대적 위치로 변환한다. N / 3은 그리드 크기를 줄여 다음 재귀 호출을 위한 준비를 한다.
   
   
5. 하위 그리드 위치 계산:
   • 그리드 분할: N x N 그리드는 3x3 하위 그리드로 나눌 수 있다.
   • 상대적 위치 결정: (x, y) 좌표가 하위 그리드 내에서 어디에 위치하는지 % 연산으로 찾는다. 예를 들어, N = 9, (x, y) = (4, 5)일 때, 결과는 (1, 2)가 되어 하위 그리드 내에서의 위치를 나타낸다.
6. 하위 그리드로의 이동: N / 3 연산으로 그리드 크기를 줄이고 다음 단계로 넘어간다.
   
   
7. 재귀적 패턴 반복: 이 과정은 전체 그리드가 N = 1인 단위 그리드로 나뉠 때까지 계속된다. 중앙 공백을 제외한 모든 곳에 별을 찍는다.

이렇게 isStar 메서드는 복잡한 프랙탈 별 패턴을 효과적으로 생성하며, printStars 메서드는 이 패턴을 출력한다.