[백준] 1030번: 프렉탈 평면 (java)

1030번: 프렉탈 평면 (acmicpc.net)

1030번: 프렉탈 평면

어떻게 생각하고 문제를 풀었는가?

각 타일에 검정색이 칠해지기 위한 조건은 다음과 같습니다.

1. 이전 시간에 의해 검정색으로 칠해져 있는가?

2. 현재 시간에서 중앙 KxK의 타일에 위치해 있는가?

 

시간 0초에서부터 s초까지 진행하며 NxN개의 재귀함수를 호출하고, s초에 도달하였을 때, 타일을 검정색 또는 흰색으로 칠하여 문제를 해결할 수 있다고 생각하였습니다.

조건으로 주어지는 R1,R2,C1,C2의 범위에 해당하는 타일만을 출력해야 하므로 범위에 해당하지 않는 타일에 대해서 재귀함수의 작업을 중단한다면 더 빠른 시간내에 정답을 찾을 수 있습니다.

코드

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

class Main {
    static int s,N,K,R1,R2,C1,C2,sSize;
    static char[][] arr= new char[51][51];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        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());

        divide(0,0,(int)Math.pow(N,s),false);

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<=R2-R1; i++){
            for(int j=0; j<=C2-C1; j++){
                sb.append(arr[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
        br.close();
    }
    static void divide(int x, int y, int size, boolean isBlack){
        if(x > C2 || x+size <= C1|| y > R2 || y+size <= R1) return;
        if(size==1){
            arr[y-R1][x-C1] = isBlack? '1': '0';
            return;
        }
        int nSize = size/N;
        int blackStart = (N-K)/2;
        int blackEnd = N-blackStart;
        for(int i=0; i<N; i++){
            int nY = y+nSize*i;
            for(int j=0; j<N; j++){
                int nX = x+nSize*j;
                divide(nX,nY,nSize, isBlack || (i >= blackStart && i < blackEnd) && (j >= blackStart && j < blackEnd));
            }
        }
    }
}

0초의 1x1의 타일에서부터 s초까지 각 타일을 NxN개의 타일로 분할하여 색을 결정하는 코드를 작성하였습니다.

분할된 타일이 조건의 s초에 도달하였을 때 범위내에 존재할 것인지 확인하기 위해서는 분할하는 재귀함수 divide의 시작 위치 x와 y가 s초에서의 타일 위치를 기준으로 작성되어야 합니다.

각 초에서 타일 1개를 이동할 때 s초에서 실제 이동한 타일의 개수를 nSize로 계산하여 x와 y좌표를 구하고, 이전 시간에서 검정색으로 칠해지는것이 확인되었거나, 현재 시간에서 검정색 타일로 분할하는 지를 boolean 값으로 넘겨 시간 s에서 각 타일의 색상을 찾을 수 있습니다.