[TopCoder] CantorDust (칸토어 분진)

칸토어 더스트는 다음과 같은 방식으로 구성된 2차원 프랙탈이다. 처음에 프랙탈은 검은 사각형이다. 각 반복에서 프랙탈의 각 사각형은 동일한 부분 제곱의 3x3 서브 그리드로 분할된다. 하위 그리드의 가운데 행 또는 가운데 열(또는 둘 다)에 속하는 검은색 하위 사각형은 흰색으로 칠합니다.
검은색과 흰색 사각형의 직사각형 패턴(각각 'X' 및 '.' 문자로 표시됨)을 나타내는 패턴이 제공됩니다. 반복 시 칸토어 분진에서 이 패턴의 발생 횟수를 반환합니다. 중복 항목이 허용됩니다.

Definition

Class:

 

CantorDust

Method:

 

occurrencesNumber

Parameters:

 

vector <string>, int

Returns:

 

int

Method signature:

 

int occurrencesNumber(vector <string> pattern, int time)

 

Examples

0)

{".X",".."}

1

Returns: 1

1)

{".."}

1

Returns: 2

2)

{"."}

2

Returns: 65

3)

{"X...X"}

2

Returns: 4

4)

{"X"}

9

Returns: 262144

---

먼저 파라미터로 프랙탈의 time과 패턴이 주어지는데

 

이 패턴이 해당 time의 프랙탈에 몇번이나 들어가 있는지 구해야한다. 

 

전체 탐색으로 풀려면 풀 수는 있지만, 시공간 복잡도 제약을 만족시키지 못할 것이다.

 

따라서 문제를 푸는 패턴을 단순화시켜서 해결해나가야한다. 

 

X		X
X		X

먼저 time 1에서의 프랙탈은 위와 같다.

 

X		X				X		X
X		X				X		X
X		X				X		X
X		X				X		X

time 2에서의 프랙탈은 time 1의 프랙탈이 4번 반복되고, 정가운데가 비어있는 형태를 취하는데 

 

time3에서의 프랙탈은 마찬가지로 time2의 프랙탈을 4번 반복한 것이다. 

 

X		X

만약 위의 형태가 패턴으로 주어지고, time 2의 프랙탈에서는 위 패턴이 6번 관찰됨을 확인할 수 있다. 

 

가만 생각해보면 프랙탈 구조는, 특정 패턴이 반복되기 때문에 이를 1차원으로 축소하여 표현할 수 있다. 

 

X

X

X

X

 

time 2에서의 프랙탈을 위의 1차원 string으로 축소하면, 이를 행과 열의 정보로 압축하여 사용할 수 있다. 

 

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

class CantorDust{
    public:
    string getFractal(int time){
        if(time==0){
            return "X";
        }
        string c = getFractal(time-1);
        return c+string(c.size(), ' ')+c;
    }

위 1차원으로 표현된 프랙탈을 구하는 함수인 getFractal이다. 

 

    int occurrencesNumber(vector <string> pattern, int time){
        int M = pattern.size(), N=pattern[0].size();
        bool a[M], b[N];
        for(int i=0; i<M; i++){
            a[i] = false;
        }
        for(int i=0; i<N; i++){
            b[i] = false;
        }

그리고 패턴의 정보를 압축하기 위해 만들어진 배열 a와 b이다. 

 

a에는 패턴의 세로 정보를, b에는 패턴의 가로 정보를 담는다. 

 

        string frac = getFractal(time);
        int len = frac.size();
        int p=0, q=0;
        bool flag = false;

프랙탈을 생성하고, 이 외 변수들을 초기화한다. 

 

        for(int i=0; i<M; ++i){
            for(int j=0; j<N; ++j){
                if(pattern[i][j]=='X'){
                    flag = true;
                    a[i] = true;
                    b[j] = true;
                }
            }
        }

패턴을 순회하면서 X가 포함된 요소의 행과 열을 true로 설정한다. 이렇게 하는 이유는 아래에 설명한다.

 

flag 변수는 패턴에 X 포함 여부를 나타낸다. 

 

왜 패턴을 훑으면서 X가 포함된 행, 열을 무조건 true로 설정할까?

 

그것은 바로 프랙탈 구조의 특징 때문이다. 

 

프랙탈은 같은 패턴이 반복되는 것이기 때문에 특정 행, 열에 X가 포함되어 있다면, 그 요소와

 

같은 행 혹은 같은 열에 있는 요소들 중 얼마든지 X가 나타날 수 있다. 

 

따라서 그 행, 열에서 X가 관찰되었다면, 그 행, 열에서 X가 관찰될 수 있음을 a, b 배열에 표시한 것이다.

 

우리는 M*N 크기의 패턴이라는 배열을 합쳐서 M+N 크기의 배열로 정보를 요약하였다.

 

        for(int i=0; i<M; ++i){
            for(int j=0; j<N; ++j){
                if((pattern[i][j] != 'X') == (a[i]&&b[j])){
                       return 0;
                }
            }
        }

하지만 패턴에 공백이 있지만, 그 행이나 열에 X가 있다고 된 경우 모순이 생긴다. 

X true	true	[공백] true	true	true
true		true
X true	true	X true	true	true

 

이 패턴 자체는 프랙탈에서 관찰될 수 없으므로 0을 반환한다.

 

        for(int k=0; k+M<=len; k++){
            bool pass = true;
            for(int x=0; x<M; x++){
                if((frac[k+x]=='X')&&a[x]==false){
                    pass = false;
                    break;
                }
                else if((frac[k+x]==' ')&&a[x]==true){
                    pass = false;
                    break;
                }
            }
            if(pass)
                p++;
        }

프랙탈과 패턴 요약정보(a)를 비교하면서 각 위치마다 서로 다른 얘기를 하고 있으면 pass를 false로 바꾼다. 

 

패턴을 한번 훑었는데 pass가 true로 살아남았으면 한번 일치한 것이므로 p를 하나 늘려준다. 

 

그리고 프랙탈의 다음 시작 위치로 한칸 옮긴다.

        for(int k=0; k+N<=len; k++){
            bool pass = true;
            for(int y=0; y<N; y++){
                if((frac[k+y]=='X')!=b[y]){
                    pass = false;
                    break;
                }
            }
            if(pass)
                q++;
        }

열에 대해서도 같은 과정을 거친다. 

 

        if(flag){
            return (p*q);
        }
        return (p*(len-N+1) + (len-M+1)*q - p*q);

패턴에 X가 포함될 경우에 p*q를 반환하고

 

패턴이 공백으로만 이루어졌을 경우 그에 맞게 반환한다.