[백준] 2630번: 색종이 만들기 - python

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

2630번: 색종이 만들기

처음에 작성한 무지성 4로 나눠 재귀하기 코드이다.

너무 비효율적이고 틀렷다고 떠서 다시 로직을 작성하였다.

n = int(input())
arr = []
blue = 0
white = 0


def paper(n, x_start, x_end, y_start, y_end):
    global blue
    global white 
    x_mid = (x_start + x_end) //2 
    y_mid = (y_start + y_end) //2 

    if n==1:
        return
    
    cnt = 0
    for i in range(y_start, y_mid+1): #4분면
        for j in range(x_start, x_mid+1):
            if arr[i][j] == 1:
                cnt+=1
    if cnt == n//2 * n//2:
        blue +=1    
    elif cnt == 0:
        white +=1
    else:
        paper(n//2, x_mid, x_end, y_mid, y_end)

    cnt = 0
    for i in range(0, y_start):
        for j in range(x_start, x_mid+1): #2분면
            if arr[i][j] == 1:
                cnt+=1
    if cnt == n//2 * n//2:
        blue +=1    
    elif cnt == 0:
        white +=1
    else:
        paper(n//2, x_mid, x_end, 0, y_start)


    cnt = 0
    for i in range(0, y_start):
        for j in range(0, x_start): #1분면
            if arr[i][j] == 1:
                cnt+=1
    if cnt == n//2 * n//2:
        blue +=1    
    elif cnt == 0:
        white +=1
    else:
        paper(n//2, 0, x_start, 0, y_start)

    cnt = 0
    for i in range(n//2, n): #3분면
        for j in range(n//2+1):
            if arr[i][j] == 1:
                cnt+=1

    if cnt == n//2 * n//2:
        blue +=1 
    
    elif cnt == 0:
        white +=1
    else:
        paper(n//2, 0, x_mid, y_mid, y_end)


for i in range(n):
    arr.append(list(map(int, input().split())))


x_start = 0
x_end = n
y_start = 0
y_end = n

paper(n, x_start, x_end, y_start, y_end)
print(blue)
print(white)

 

위와 차이점은 위는 무조건 4개씩 나눠야된다는 관점하에 작성한 코드이고 아래는 통으로 재귀를 돌리는 코드이다. 

 

확실히 보기 좋고 깔끔한 코드인것 같다.

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
blue = 0
white = 0

def count_color_paper(x, y, size):
    global blue, white
    initial_color = arr[y][x]
    for i in range(y, y + size):
        for j in range(x, x + size):
            if arr[i][j] != initial_color:  # 현재 구역의 색이 모두 같지 않으면
                # 4개의 구역으로 나누어 각 구역에 대해 재귀적으로 함수 호출
                new_size = size // 2
                count_color_paper(x, y, new_size)  # 1분면
                count_color_paper(x + new_size, y, new_size)  # 2분면
                count_color_paper(x, y + new_size, new_size)  # 3분면
                count_color_paper(x + new_size, y + new_size, new_size)  # 4분면
                return  # 추가 분할 후에는 현재 함수 종료

    # 현재 구역이 모두 같은 색으로 되어 있다면
    if initial_color == 1:
        blue += 1
    else:
        white += 1

# 프로그램의 메인 로직 실행 부분
count_color_paper(0, 0, n)  # 전체 종이에 대해 함수 호출

# 결과 출력
print(white)
print(blue)

 

완성