[백준/파이썬] 2630번 색종이 만들기 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 2630번 색종이 만들기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

정사각형 색종이가 주어질 때 같은 색으로만 이루어진 종이 개수(흰색/파란색)를 구하는 문제입니다.

코드

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

for _ in range(n):
    paper.append(list(map(int, input().split())))

def cut(x, y, length):
    global paper, blue, white
    
    if length == 1:
        if paper[x][y] == 1:
            blue += 1
        else :
            white += 1
        return
    
    flag = False
    i = x
    while i < x + length:
        j = y
        while j < y + length:
            flag = paper[x][y] != paper[i][j]
            if flag:
                break
            j += 1
        if flag:
            break
        i += 1

    if flag:
        tmp = length // 2
        cut(x, y, tmp)
        cut(x, y + tmp, tmp)
        cut(x + tmp, y, tmp)
        cut(x + tmp, y + tmp, tmp)
    else:
        if paper[x][y] == 1:
            blue += 1
        else :
            white += 1
        return

cut(0, 0, n);
print(white)
print(blue)

설명

현재 영역이 단색이면 바로 카운트하고, 아니면 4등분으로 재귀 분할해 같은 과정을 반복합니다.

---

• 백준 문제풀이 전체 목록 보기

---