★DAC 중상급1 - 3문제()★

🍴 DAC 분할정복 문제는 주로 재귀를 사용해 여러 개의 sub-problem을 돌리고 차례차례 해결해나가는 경우가 많다. 중상급 이상의 난이도부터 차례대로 탐색해보자!

 

🍴 아래 DAC 이론 포스팅 참조

Divide&Conquer(DAC)

---

★ 2630 색종이 만들기 ★

 

import sys
input=sys.stdin.readline

N=int(input())
W,B=0,0
confetti=[]

def is_check(arr):
    side=len(arr)
    if all(arr[i][j] == 0 for i in range(side) for j in range(side)):
        return 'W'
    elif all(arr[i][j] == 1 for i in range(side) for j in range(side)):
        return 'B'
    else: return 0

def get_confetti(arr,l,W,B):
    if l == 1:
        if arr[0][0] == 0:
            W+=1
            return (W,B)
        else:
            B+=1
            return (W,B)
    else:    
        if is_check(arr) == 'W':
            W+=1
            return (W,B)
        elif is_check(arr) == 'B':
            B+=1
            return (W,B)
        else:
            border = l//2
            arr1,arr2,arr3,arr4=[],[],[],[]
            
            for i in arr[:border]:
                arr1.append(i[:border])
                arr2.append(i[border:])
            for j in arr[border:]:
                arr3.append(j[:border])
                arr4.append(j[border:])
            W,B = get_confetti(arr1,border,W,B)
            W,B = get_confetti(arr2,border,W,B)
            W,B = get_confetti(arr3,border,W,B)
            W,B = get_confetti(arr4,border,W,B)
    return (W,B)


    
for _ in range(N):
    confetti.append(list(map(int,input().split())))

l = len(confetti)

W,B = get_confetti(confetti,l,0,0)
print(W,B,sep='\n')

 

🍴 주어진 정사각형이 모두 1로 이루어져 있는지, 0으로 이루어져 있는지 확인하는 sub-problem으로 분할할 수 있으며, 한 번 확인된, 즉 한 번 해결된 sub-problem은 이후 다시 풀게 되는 경우가 없으므로 분할정복 DAC 알고리즘이라 할 수 있다.

 

🍴 재귀를 사용 시 주의점 - 동일 함수를 재귀적으로 여러 번 쓸 때마다, 변수 W, B가 계속 초기화되므로 새롭게 생기는 sub-problem을 해결할 때마다 W,B 변수에 계속 update해줘야 한다.

---

★ 1780 종이의 개수 ★

 

import sys
input=sys.stdin.readline

N=int(input().rstrip())
papers=[list(map(int,input().split())) for _ in range(N)]

cnt_dic={'-1':0, '0':0, '1':0}
l=len(papers)

def check_the_same(arr):
    cmp=arr[0][0]
    l=len(arr)
    flag=True
    for i in range(l):
        for j in range(l):
            if arr[i][j] != cmp:
                flag = False
                return (False,2)
    if flag:
        return (True,cmp)

def cut_paper(arr,l):
    if l == 0:
        res,val=True,arr[0]
    else:
        res,val = check_the_same(arr)

    if res:
        if val == -1: cnt_dic['-1']+=1
        elif val == 0: cnt_dic['0']+=1
        else: cnt_dic['1']+=1
        return
    
    else: #if False, recursion
        #divide into 9 pieces
        l=len(arr)
        if l > 0:
            arrays=[[] for _ in range(9)]
            for i in arr[:l//3]:
                arrays[0].append(i[:l//3])
                arrays[1].append(i[l//3:(2*l)//3])
                arrays[2].append(i[(2*l)//3:l])
            
            for i in arr[l//3:(2*l)//3]:
                arrays[3].append(i[:l//3])
                arrays[4].append(i[l//3:(2*l)//3])
                arrays[5].append(i[(2*l)//3:l])

            for i in arr[(2*l)//3:l]:
                arrays[6].append(i[:l//3])
                arrays[7].append(i[l//3:(2*l)//3])
                arrays[8].append(i[(2*l)//3:l])

            for subarr in arrays:
                cut_paper(subarr,l//3)

        return
    
cut_paper(papers,len(papers))

print(cnt_dic['-1'])
print(cnt_dic['0'])
print(cnt_dic['1'])

 

🍴 위와 동일한 전형적인 분할정복 문제로, 분할하고, recursion을 반복해 정복 유형으로 해결한다.

 

🍴 다만, arr의 개수가 1개일 경우, 바로 값을 출력하게 하였고, 전체 -1의 개수, 0의 개수, 1의 개수를 매번 업데이트하며 재귀함수의 매개변수로 넣지 않은 대신, 각 종류의 개수를 딕셔너리 자료형으로 만들어 개수를 업데이트하는 형식으로 코드 진행

 

🍴 전체 arr 자체를 쪼개기 보다는, indexing으로 arr의 간격 size를 조절하는 방식으로 진행한다면 더 효율적으로 짤 수 있다.

(for문에서 arr자체를 반복하기 보다, length 사이즈 자체를 반복하는 것이 더 효율적인 것 처럼)

---

★ 1074 Z ★

 

import sys
N,r,c=map(int,input().split())
size = 2**N
global n
n = 0
i,j=0,0

def if_size_two(i,j):
    if (i,j) == (r,c):
        print(n)
        sys.exit()
    elif (i,j+1) == (r,c):
        print(n+1)
        sys.exit()
    elif (i+1,j) == (r,c):
        print(n+2)
        sys.exit()
    else:
        print(n+3)
        sys.exit()

def divide_into_four(i,j,size):
    global n
    if size == 2:
        if_size_two(i,j)
    else:
        #1
        if i<=r<(i+size//2) and j<=c<(j+size//2):
            divide_into_four(i,j,size//2)
        else:
            n+=((size//2)*(size//2))
		
        #2
        if i<=r<(i+size//2) and j+size//2<=c<(j+size):
            divide_into_four(i,j+size//2,size//2)
        else:
            n+=((size//2)*(size//2))
        
        #3
        if i+size//2<=r<(i+size) and j<=c<(j+size//2):
            divide_into_four(i+size//2,j,size//2)
        else:
            n+=((size//2)*(size//2))
        
        #4
        if i+size//2<=r<(i+size) and j+size//2<=c<(j+size):
            
            divide_into_four(i+size//2,j+size//2,size//2)
        else:
            n+=((size//2)*(size//2))

divide_into_four(i,j,size)

 

🍴 Z 탐색 흐름

→ 위 왼쪽 → 위 오른쪽 → 아래 왼쪽 → 아래 오른쪽 방향 순서로 탐색이 진행된다.

 

🍴 pseudo-code 흐름

① size(정사각형 한 변의 길이)가 2이면 위 Z 순서로 일치하는 (r,c) 파악하고 바로 sys.exit()으로 종료!

② size가 2가 아니라면 4등분 → Z 순서로 위 왼쪽부터 차례대로 target이 있는 지 확인

≫ (1) 있다면 ①부터 다시 재귀 → 있는 곳만 계속 팜 (depth-first search)

≫ (2) 없다면 전역변수 n 그만큼 size를 2로 나눈 값의 제곱을 더하고, 그 다음 방향 탐색 (반드시 target이 4등분한 곳 중 한 군데에 있음)

※ 주의점! 4등분할 때 마다 시작점 (i,j)가 계속 바뀌므로 update한 (i,j)를 재귀함수 인자에 넣어주어야 한다

※ 반드시 pseudo-code 흐름을 먼저 그린 다음 코딩 진행하기

 

🍴 시간초과 코드

import sys
N,r,c=map(int,input().split())
size = 2**N
global n
n = 0
i,j=0,0
flag=False

def draw_Z(i,j,size):
    if size==2:
        global n
        if i<=r<=(i+1) and j<=c<=(j+1):
            if (i,j) == (r,c):
                flag = True
                print(n)
                sys.exit()
            elif (i,j+1) == (r,c):
                flag = True 
                print(n+1)
                sys.exit()
            elif (i+1,j) == (r,c):
                flag = True 
                print(n+2)
                sys.exit()
            else:
                flag = True
                print(n+3)
                sys.exit()
        n += 4
        return
    else:
        draw_Z(i,j,size//2)
        draw_Z(i,j+size//2,size//2)
        draw_Z(i+size//2,j,size//2)
        draw_Z(i+size//2,j+size//2,size//2)

draw_Z(i,j,size)

 

→ 너무 많이 깊게 들어간다. 쓸데없이 깊게 들어간다.

 

→ 원하는 target이 예를 들어 35라면, 시간초과 코드는 길이가 2인 정사각형을 차례대로 일일이 다 알아보고 일명 노가다성으로 계속 탐색한다.

→ 하지만 맞힌 코드는 target이 들어간 가장 큰 정사각형 먼저 들어가고, target이 들어간 그 다음 큰 정사각형만 들어가는 등 재귀 호출의 횟수가 현저히 적다.

---