백준 2630색종이자르기

분할정복을 잘못이해해서 나중에 실수 하지 않도록 남겨노려고함..!

# 색종이만들기
# z처럼 일단 좌표로 풀어,,>나눠 나눠 좌표 이동 할 필요가 이씅ㄹ 까 있나 있나보다 !
# 두가지 경우 1/4로 분할을때 모든 같은 숫자인지 판별  아 한가지 경우구나 어차피
# 왜나면 크기가 1까지 작아지면 결국 똑같이 만든 함수로 판별 가능
import sys

sys.setrecursionlimit(10**9)
n=int(input())

input_list=[list(map(int,input().split())) for _ in range(n)]

w,b=0,0
# print(input_list)

def quarter(n,dimension,arr):
    #재귀 들어왔을때 모두 동일한 숫자인지 판별하는 로직
    # 그게 아니라면 1/4해서 다시 각각 판별해야함
    global w,b
    answer_list=isSameNumber(arr,dimension,n)
    if answer_list[0]:
        if answer_list[1]==0:
            w+=1
        else:
            b+=1
        return
    mid=n//2
    # 1
    quarter(mid,1,arr)
    # 2
    quarter(mid,2,arr)
    # 3
    quarter(mid,3,arr)
    # 4
    quarter(mid,4,arr)


def isSameNumber(arr:list,d,n)->list:
    #  1 은 가장 처음 에 1차원이라고 해서 넣어주면 판별가능
    # 내가 시작 인덱스를 너무 안일하게 생각 했구나 ㄱ ㅅㄱㅅㄱㅅ
    
    return_list=[]
    if d==1:
        initial_num =arr[0][0]
        for i in range(n):
            for j in range(n):
                if arr[i][j]!=initial_num: # 이러면 크기가 하나일때 비교가 되나 ? i문만 들어가겠죠 ~  j 안돌겠져
                    return_list.append(False)
                    return_list.append(initial_num)
                    return return_list
        return_list.append(True)
        return_list.append(initial_num)
        return return_list
    elif d==2:
        initial_num = arr[0][n]
        for i in range(n):
            for j in range(n,2*n):
                if arr[i][j]!=initial_num: # 이러면 크기가 하나일때 비교가 되나 ? i문만 들어가겠죠 ~  j 안돌겠져
                    return_list.append(False)
                    return_list.append(initial_num)
                    return return_list
        return_list.append(True)
        return_list.append(initial_num)
        return return_list
    elif d==3:
        initial_num = arr[n][0]
        for i in range(n,2*n):
            for j in range(n):
                if arr[i][j]!=initial_num: # 이러면 크기가 하나일때 비교가 되나 ? i문만 들어가겠죠 ~  j 안돌겠져
                    return_list.append(False)
                    return_list.append(initial_num)
                    return return_list
        return_list.append(True)
        return_list.append(initial_num)
        return return_list

    elif d==4:
        initial_num = arr[n][n]
        for i in range(n,2*n):
            for j in range(n,2*n):
                if arr[i][j]!=initial_num: # 이러면 크기가 하나일때 비교가 되나 ? i문만 들어가겠죠 ~  j 안돌겠져
                    return_list.append(False)
                    return_list.append(initial_num)
                    return return_list

        return_list.append(True)
        return_list.append(initial_num)
        return return_list



quarter(n,1,input_list)

print(w)
print(b)

 

 

분할할때 분할 범위를 안주고 그냥 차원 만줘서 탐색하려고 햇는데  4*4이하에서만 생각해서 모든 색종이 경우의수가. 잘나오는데

문제의 입력예제를 돌리면 다른 출력이 나와서 한참 고민하다가 결국 gpt힘을 빌렷다..

gpt는 그냥 계속 범위를 지정해서 전달해줘야한다고해서 나는 그걸 이해 못하고... 아니 차원만 넘겨받아서 for문 돌릴때 돌리는 범위를 제한 하면 되는거 아닌가 생각했는데.... 

생각해보니 8*8이상에서 생각해보면 상대적인 각 차원의 상대적인 위치도 고려해줘야해서.. 그래서 함수 호출할때 시작 끝 범위를 넘겨 줘야 된다고 한듯..!

 

 

수정된 부분이다

각 차원마다 시작 보정값과 for문을 돌아갈때 늘어난 보정값만 큼 끝값을 늘려줬다.

하지만 아직도 for문 범위를 정하는건 힘들다...!!

 mid=n//2
    ## 각 주어진 점은 시작 점인가 ? ₩~~~
    # 1
    quarter(mid,x,y,arr)
    # 2
    quarter(mid,x,y+mid,arr)
    # 3
    quarter(mid,x+mid,y,arr)
    # 4
    quarter(mid,x+mid,y+mid,arr)


def isSameNumber(arr:list,x,y,n)->list:
    #  1 은 가장 처음 에 1차원이라고 해서 넣어주면 판별가능
    # 내가 시작 인덱스를 너무 안일하게 생각 했구나 ㄱ ㅅㄱㅅㄱㅅ
    return_list=[]
    #시작하는 첫번재 값 ...
    initial_num =arr[x][y]
    for i in range(x,n+x):
        for j in range(y,n+y):
            if arr[i][j]!=initial_num: # 이러면 크기가 하나일때 비교가 되나 ? i문만 들어가겠죠 ~  j 안돌겠져
                return_list.append(False)
                return_list.append(initial_num)
                return return_list
    return_list.append(True)
    return_list.append(initial_num)
    return return_list