백준 - 2630번(재귀,분할정복)

핵심 아이디어는 다음과 같다.

1. 입력은 무조건 2^n개로 주어지기 때문에 처음 주어진 전체 길이에서 반씩 분할 정복해나가면 된다.

 

2. 분할은 무조건 4개로 하면된다. 가장 작은 경우인 길이가 2일 때도 원소 1개씩 해서 4개의 사각형으로 나눠 지기 때문

 

3. 4분할 기능을 하는 함수를 만들고 이를 조건에 맞게 재귀로 반복 호출하면 된다.

 

4. 우선 함수의 실행조건은 처음 사각형의 크기가 1보다 커야 하고 0과 1 둘 다 한 개 이상씩 포함해야 한다.

이 조건을 지키지 않아서 한번 실패를 했는데 예를들어 길이 2짜리 사각형(1,1,1,1) 이 주어지면 내 함수는 이거를 각 (1), (1), (1), (1) 이렇게 4개의 사각형으로 분해해 버린다. 따라서 위 조건을 추가했다.

 

5. 재귀를 호출하는 조건도 위와 같다. 사각형에 0과 1 둘다 한 개 이상씩 포함해야 한다. 그렇지 않을 경우 모든 원소가 동일한 경우이므로 첫 번째 원소가 1인지 0인지 판단해서 색상을 ans 배열에 넣어준다.

 

6. ans배열에 각 w와 b 원소가 몇개인지 카운트해서 출력한다.

 

import sys

n = int(sys.stdin.readline().strip())
arr = []
for i in range(n):
    arr.append(sys.stdin.readline().strip().split())
b = 0
w = 0
ans = []
def cut(arr):
    if len(arr[0]) > 1 and '0' in sum(arr,[]) and '1' in sum(arr,[]):
        a = len(arr[0]) / 2 #이전 사각형의 절반만큼으로 자르기
        a = int(a)
        temp1 = []
        temp2 = []
        temp3 = []
        temp4 = []

        for i in range(a): #사각형 4분할
            temp1.append(arr[i][:a]) 
            temp2.append(arr[i][a:])
            temp3.append(arr[i + a][:a])
            temp4.append(arr[i + a][a:])

        if '0' in sum(temp1,[]) and '1' in sum(temp1,[]):
            cut(temp1)
        else:
            if temp1[0][0] == '1':
                ans.append('b')
            else:
                ans.append('w')

        if '0' in sum(temp2,[]) and '1' in sum(temp2,[]):
            cut(temp2)
        else:
            if temp2[0][0] == '1':
                ans.append('b')
            else:
                ans.append('w')

        if '0' in sum(temp3,[]) and '1' in sum(temp3,[]):
            cut(temp3)
        else:
            if temp3[0][0] == '1':
                ans.append('b')
            else:
                ans.append('w')

        if '0' in sum(temp4,[]) and '1' in sum(temp4,[]):
            cut(temp4)
        else:
            if temp4[0][0] == '1':
                ans.append('b')
            else:
                ans.append('w')

    else:
        if arr[0][0] == '1':
            ans.append('b')
        else:
            ans.append('w')

cut(arr) #함수실행
b = ans.count('b') #파란색 개수
w = ans.count('w') #하얀색 개수
print(w)
print(b)