213. 색종이 자르기[분할 정복]

1) 어떤 전략(알고리즘)으로 해결?

분할 정복

2) 코딩 설명

<내 풀이>

import sys

n = int(sys.stdin.readline().rstrip())
mapp = []
for i in range(n) : 
    mapp.append(list(map(int, sys.stdin.readline().split())))

cnt_zero=0; cnt_mn=0; cnt_pl=0

# 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용

def all_same(rr,cc,length_of_side): # r,c 는 맨 왼쪽 꼭지점 
    chk = mapp[rr][cc]

    for i in range(rr, rr+length_of_side) :
        for j in range(cc, cc+length_of_side) :
            if mapp[i][j]!=chk : return False
    else : return True

# 9개로 자르고 
def nine_cut(r,c,length_of_side) : 

    global cnt_zero,cnt_mn,cnt_pl

    if all_same(r,c,length_of_side) : 
        
            
        # 이 종이의 처음 아이 구해서
        if mapp[r][c] == 0 : cnt_zero+=1
        elif mapp[r][c] == 1 : cnt_pl+=1
        else : cnt_mn+=1

    else : 
        for i in range(3) :
            for j in range(3) :
                nine_cut(
                    r+(length_of_side//3)*i, //이거 넘겨주는 부분을 잘못 썼었음
                    c+(length_of_side//3)*j,
                    length_of_side//3
                    )

nine_cut(0,0,n)

print(cnt_mn); print(cnt_zero); print(cnt_pl)

<내 틀렸던 풀이, 문제점>

import sys

n = int(sys.stdin.readline().rstrip())
mapp = []
for i in range(n) : 
    mapp.append(list(map(int, sys.stdin.readline().split())))

# 지도 안에 -1,0,1 갯수
def cnt_mapp(mapp) :
    res_minus=0; res_zero=0; res_plus=0
    for m in mapp :
        for mm in m :
            if mm==-1 : res_minus+=1
            elif mm==0 : res_zero+=1
            else : res_plus+=1
    return res_minus, res_zero, res_plus


# 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용
def all_same(mapp):
    impossible = False
    chk = mapp[0][0]
    for m in mapp:
        if impossible: break
        for mm in m :
            if mm!=chk : 
                impossible=True;break
    return impossible

# 9개로 자르고 
def nine_cut(mapp) : 
    lenn = len(mapp)
    for i in range(3) :
        for j in range(lenn*i, lenn*i+3) : 
            # 012 345 678 일케 나눈 상황
            for k in range(3) :
                for w in range(lenn*i, lenn*i+3) : 
                    mapp[j][w]

        
    

if all_same(mapp) : m,z,p = cnt_mapp(mapp); print(m);print(z);print(p)
else : 

• 9분할로 나누는 함수 how 구현?

아이디어 출처 : https://zidarn87.tistory.com/385

map을 직접 잘라서 아예 new map으로 만든다는 생각 X,

그냥 인덱스로만 비교해주면 되지롱

import sys

n = int(sys.stdin.readline().rstrip())
mapp = []
for i in range(n) : 
    mapp.append(list(map(int, sys.stdin.readline().split())))

cnt_zero=0; cnt_mn=0; cnt_pl=0

# 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용

def all_same(r,c,length_of_side): # r,c 는 맨 왼쪽 꼭지점 
    chk = mapp[r][c]
    for i in range(r, r+length_of_side) :
        for j in range(c, c+length_of_side) :
            if mapp[i][j]!=chk : return False
    else : return True


def cnt_map(r,c,length_of_side) : 
    global cnt_zero,cnt_mn,cnt_pl

    # all same 이면 이제 그 구간은 불변이므로 갯수세주기
    for i in range(r, r+length_of_side) :
        for j in range(c, c+length_of_side) :
            if mapp[i][j] == 0 :
                cnt_zero+=1
            elif mapp[i][j] ==1 :
                cnt_pl+=1
            else : cnt_mn +=1
    

# 9개로 자르고 
def nine_cut(r,c,length_of_side) : 
    if all_same(r,c,length_of_side) : 
        cnt_map(r,c,length_of_side)
    else : 
        for i in range(3) :
            for j in range(3) :
                nine_cut(r//3+i*3,c//3+j*3,length_of_side//3)

nine_cut(0,0,n)

print(cnt_mn); print(cnt_zero); print(cnt_mn)

• 근데 테스트 케이스부터 틀리는 중~

<반성 점>

• 뭔가 쪼갠다고 할 때 그 쪼개진 map을 진짜 구하려고 하지 말구 구간만 알면 가능
• 그리고 뭘 세는지 파악을 잘못해서 시간을 넘 많이 소요 ! 속상~

<배운 점>

what is 분할정복?

재귀적으로 함수 호출하면서 큰 문제를 작은 문제로 나눠가며 해결하는 알고리즘

• 파이썬의 경우 sys.setrecursionlimit(10**5) 로 재귀깊이 설정 필요
• 재귀를 사용하자