본문 바로가기
[개발] 알고리즘

백준 2448 - 별찍기 11(Fractal: 프랙탈) 자바로 풀기

by Devsong26 2017. 11. 17.

설명을 하기 앞서 참고한 소스코드의 출처를 밝힙니다. 

출처: http://stompesi.tistory.com/32#comment12022832

 

Fractal이란? (출처: http://terms.naver.com/entry.nhn?docId=933753&cid=43667&categoryId=43667)

작은 구조가 전체 구조와 비슷한 형태로 끝없이 되풀이 되는 구조를 말합니다. 

(아래와 같은 그림을 프랙탈(Fractal)이라고 하며 다양한 형태가 존재합니다.)

 

문제 출처: https://www.acmicpc.net/problem/2448

 

제시된 문제를 보시면 입력은 자연수 N이 입력됩니다. 

이 때, N은 항상 3*2^k(3, 6, 12, 24, 48, ...) (k<=10) 입니다. 

 

아래는 출력 예시입니다. 

사각형 표시는 제가 한 것입니다.

보시면 맨 위의 빨간색 사각형(N=3)안에 있는 삼각형이 기본 삼각형입니다. 

그리고 그 밑에 빨간색 사각형을 이어붙입니다.

이 것이 N=6인 Fractal 삼각형 모형입니다.

 

위의 세개의 빨간색 사각형을 하나의 보라색 사각형으로 표시합니다. 

그리고 그 밑에 보라색 사각형을 이어붙입니다.

이 것이 N=12 Fractal 삼각형 모형입니다. 

 

위의 세개의 보라색 삼각형을 하나의 초록색 사각형으로 표시합니다. 

그리고 그 밑에 초록색 사각형을 이어붙입니다. 

이 것이 N=24 Fractal 삼각형 모형입니다. 

 

사각형으로 표시한 이유는 삼각형을 표시하는 '*', 그 사이의 공백을 표시하기 위합니다.

 

Fractal 삼각형의 특징은 맨 위의 "*" 양 옆의 공백은 2*N-1입니다. 

그 후, N-1줄까지 줄을 나타내는 변수값이 1증가할 때마다 좌우 공백이 1씩 줄어듭니다. 

 

코드에서는 String 배열, 공백 문자열을 이용하여 문제를 해결하면 됩니다. 

 

String 문자열을 주어진 입력인 N의 크기로 생성합니다. 

String[0] = "  *  ";

String[1] = " * * ";

String[2] = "*****";

이 후, 0,1,2 index의 element를 초기화시킵니다. 

 

N = 6 Fractal을 표시하는 경우, 1,2,3줄은 기본 삼각형을 그립니다.

4,5,6줄은 1,2,3줄을 이용하여 2개의 기본 삼각형을 그립니다. 

위의 설명에서는 사각형 두개를 이어붙인다고 했지만 코드상에서는 그것이 사각형+사각형으로 구현할 수는 없습니다. 

두개의 사각형 최상단 부터 그리면서 최하단까지 내려와야 합니다. 

String[3] = String[0] + " " + String[0];

String[4] = String[1] + " " + String[1];

String[5] = String[2] + " " + String[2];

이런식으로 그립니다. 

 

위의 과정을 거치면 아래와 같이 배치됩니다.

이제 우리는 1,2,3줄의 String 좌우에 공백을 더해주어 정상적인 형태를 맞춰주어야 합니다. 

 

이 때, 좌우 공백으로 입력되는 공백의 길이는 N/2입니다. N=6일 경우는 공백이 3칸입니다.

아래와 같이 하시면 됩니다. 

String[0] = "   " + String[0] + "   "; // "     *     "

String[1] = "   " + String[1] + "   "; // "    * *    "

String[2] = "   " + String[2] + "   "; // "   *****   "

그러면 아래와 같이 출력됩니다. 

 

이 후에는 위의 작업을 반복합니다. 

 

아래는 소스코드입니다. 

import java.io.*;

public class Main{

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int n = Integer.parseInt(br.readLine().trim());

br.close();

int h = 3, j, m=1;

String[] arr = new String[n];

arr[0] = "  *  ";

arr[1] = " * * ";

arr[2] = "*****";

String ws = "     ";

for(; h<n; h<<=1, m<<=1){

for(j=0; j<h; j++){

arr[h + j] = arr[j] + " " + arr[j];

arr[j] = ws + arr[j] + ws;

}

for(j=0; j<m; j++){

ws += "     ";

}

}

for(int i=0; i<arr.length; i++){

bw.write(arr[i]);

bw.write("\n");

}

bw.flush();

bw.close();

}

}

 

 

변수 설명

- h는 높이를 저장하는 변수입니다. 

for문의 반복될 때마다 2배식 증가합니다. 

- m은 공백을 증가시켜줄 때 사용하는 반복 변수입니다. h 증가 후 두배로 증가합니다. 

- j는 반복변수입니다. 

 

 

이상으로 포스팅을 마칩니다.