CantorDust

문제

검은 정사각형에서 3x3 으로 분할되는 칸토어 먼지라는 프렉탈이 있다

흑색을 'X', 백색을 '.' 로 표현하는 string[] pattern 이 주어질때,

반복 횟수 time 의 칸토어 먼지에서 패턴 매칭 횟수를 리턴한다
(부분적으로 겹치는 매칭도 허용)

time : 1 ~ 9

예시 입력

1)
{
    ".X", 
    ".."
},
1

2)
{
    ".."
},
1

3)
{
    "."
},
2

4)
{
    "X...X"
},
2

5)
{
    "X"
},
9

예시 출력

1
2
65
4
262144

생각의 변화

time 9 까지 가능

가로 3^9 (19683) 세로 3^9 (19683), 2차원 배열 불가

식으로 나타내는 법

중복이니까 [0][0] 부터 하면 너무 범위가 커지는

프렉탈, 같은 구조가 반복된다.

패턴 매칭에 사용가능한 규칙이 필요

단위를 나누기가 쉽지 않다는 생각

가로 세로 대칭성을 이용

2차원 배열을 1차원 배열 2개로 표현
둘다 검정이면 검정

패턴등장 체크를 만약 2행이면

i, j 를 고정해두고 패턴 내에서 이동하면서 체크

X 일때는 r[i] == X && c[j] == X
. 일떄는 r[i] == . || c[j] == .

pseudo code

checkPattern(const string &row, const string &column, vector<string> pattern, int r, int c, int width, int height)
    for (i=0  i<height  i++)
        for (j=0  j<width  j++)
            if (pattern[i][j] == 'X')
                if (row[r+i] == 'X'  &&  column[c+j] == 'X')
                    // matched
                else
                    return false

            else if (pattern[i][j] == '.')
                if (row[r+i] == '.'  ||  column[c+j] == '.')
                    // matched
                else
                    return false

    return true

occurrencesNumber(pattern, time)
    string column = ""
    string row = ""
    
    string box = "X"
    string space = "."
    
    for (i=0; i<time; i++)
        box = box + space + box
        space = space + space + space
        
    column += box
    column += space
    column += box
    
    row = column
    
    width = pattern[0].size()
    height = pattern.size()

    n = pow(3, time)
    
    matched = 0
    
    for (i=0  i<=n-height  i++)
        for (j=0  j<=n-width  j++)
            if (checkPattern(row, column, pattern, i, j, width, height))
                matched++
                
    return matched

마지막 예제 시간초과

마지막 예제에서는 19683 x 19683 번 검사하면서, 2초를 넘긴다

생각의 변화

2차원 pattern 을 1차원 row[], col[] 로 변경한다.
행 row[i] 에 X 가 있는지, 열 col[j] 에 X 가 있는지 담아둔다

2차원 프렉탈을 1차원 패턴 C 로 변경한다.
가로와 세로가 동일한 모양이기 때문에 가능

열 마다 탐색해서, 열 끝까지 탐색이 되면 q++
행 마다 탐색해서, 행 끝까지 탐색이 되면 p++

탐색이 끝나는 조건은

(C[i+k] == X) != row[k]
(C[j+k] == X) != col[k]

pattern 에 X 가 있다면 발견된 p 와 q 를 곱하면 매칭 갯수가 된다

하지만 X 가 없다면 매칭된 곳마다, 프랙탈 길이와 패턴 길이에 의한 식이 곱해져야 한다

패턴 세로를 M, 가로를 N, C 길이를 L 이라고 할때

p*(L-N+1) + q*(L-M+1)

p*(L-N+1)
탐색된 행의 갯수 * 한 행에서 가능한 경우

q*(L-M+1)
탐색된 열의 갯수 * 한 열에서 가능한 경우

이때 생각해봐야 하는게 있다,
가로마다 세로마다 체크했으니, 분명 중첩되는 곳이 있을것이다

중첩되는곳은 행 하나에서 q 번 매칭됬을것이다.
행은 p 번 매칭되었으므로

중복된 곳은 p*q 가 된다.

pseudo code

string getString(int time)
    if (time == 0)
        return "X"
    
    string s = getString(time-1)
    
    return s + string(s.size(), '.') + s

occurrencesNumber(pattern, time)
    M = pattern.size()
    N = pattern[0].size()
    
    vector<bool> row(M, false)
    vector<bool> col(N, false)
    
    bool flag = false
    
    for (r=0  r<M  r++)
        for (c=0  c<N  c++)
            if (pattern[r][c] == 'X')
                row[r] = col[c] = flag = true
                
    string s = getString(time)
    
    L = s.size()
    p = 0, q = 0

    for (r=0  r+M<=L  r++)
        int k
        
        for (k=0  k<M  k++)
            if ((s[r+k] == 'X') != row[k])
                break
                
        if (k == M)
            p++
            
    for (c=0  c+N<=L  c++)
        int k
        
        for (k=0  k<N  k++)
            if ((s[c+k] == 'X') != col[k])
                break
                
        if (k == N)
            q++
            
    if (flag)
        return p*q
    else
        return p*(L-N+1) + q*(L-M+1) - p*q