[PY] : 2630 색종이 만들기

https://www.acmicpc.net/problem/2630

2 ** (m -1)과  2 ** m - 1을 헷갈려서 다소 얼탄 문제였다. 구상한 내용은 다음과 같다 :

1. 시작하는 지점의 내용을 따로 기억해둬야한다. 이 내용은 코드에서 pivotValue 로 구현되었다.
2. pivotValue와 다른 내용이 있는 경우가 있는지 주변 구역을 확인하다. 이 문제에서는 정사각형 단위로 끊어지게끔 구현되었다.
   1. 순회에서 바뀐 내용이 없는 경우 해당 구역은 pivotValue와 모두 동일한 내용이라고 간주 할 수 있다. 결과값을 갱신한다.
   2. for문에서 변동 내용이 감지 될 수 있다. 이 때 구역을 상세하게 나눠서 한 단계 깊은 재귀 함수가 실행된다.
      • 여기서는 맨 윗 단계의 1-2를 반복한다.

lineLength = int(input())
field = [list(map(int,input().strip().split())) for _ in range(lineLength)]
colorCnt = [0, 0]

def func(m, x, y):
    isDiff = False
    pivotValue = field[x][y]
    if(m == 0):
        colorCnt[pivotValue] += 1
        return


    for i in range(x, x + (2 ** m)):
        for j in range(y, y + (2 ** m)):
            if(field[i][j] != pivotValue):
                isDiff = True
            
            if(isDiff):
                break

        if(isDiff):
            break
    
    if(isDiff):
        func(m-1, x, y)
        func(m-1, x + (2 ** (m - 1)), y)
        func(m-1, x, y + (2 ** (m - 1)))
        func(m-1, x + (2 ** (m - 1)), y + (2 ** (m - 1)))
                                           
                                           
    else:
        colorCnt[pivotValue] += 1
        return

# input 구성하고, 제곱 수 만드는 방법 생각해두기

tmpVal = lineLength
multipleVal = 0
while tmpVal != 1:
    multipleVal += 1
    tmpVal = tmpVal // 2

func(multipleVal, 0, 0)

print(colorCnt[0])
print(colorCnt[1])