[파이썬] 백준 2630 : 색종이 만들기 (python)

문제 출처

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

2630번: 색종이 만들기

* 체크 리스트

---

시간

1. 즉시 작성 가능
2. 1시간 이내
3. 1시간 이상
4. 하루 이상

이해도

1. 이해 완료
2. 복습 필요
3. 부분 이해
4. 이해 불가

체감 난이도

1. 최상
2. 상
3. 중
4. 하
5. 최하

---

문제

흰 종이의 개수 및 파란색 종이의 개수를 출력하시오.

나누는 방법

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형 칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

---

전체 코드

# 변수 받음
N = int(input())
# 횟수 카운트 선언
count_blue = 0
count_white = 0
# 조건을 그래프로 받음
graph = [list(map(int, input().split())) for _ in range(N)]

# 쿼드 선언


def quad(x, y, n):
    # 그래프의 [x][y]값을 확인하겠다.
    check = graph[x][y]
    # 전역변수 사용하겠다 선언
    global count_white, count_blue
    # 범위 x부터 x+n까지 루프를 돈다
    for i in range(x, x+n):
        # 범위 y부터 y+n까지 루프를 돈다
        for j in range(y, y+n):
            # 만약 check값이 graph의 {ex)graph[0][2] = 0}과 같지 않다면
            # check값을 -1로 바꾸고 반복문을 정지(break)한다.
            if check != graph[i][j]:
                check = -1
                break
    # 만약 check값이 -1이라면 n을 2로 나눈다.
    if check == -1:
        n //= 2
        # 좌측 상단
        quad(x, y, n)
        # 우측 상단
        quad(x, y+n, n)
        # 좌측 하단
        quad(x+n, y, n)
        # 우측 하단
        quad(x+n, y+n, n)

    # 만약 check값이 1이면 count_blue를 1더함
    elif check == 1:
        count_blue += 1
    # 만약 check값이 0이면 count_blue를 1더함
    elif check == 0:
        count_white += 1


quad(0, 0, N)

# 출력함
print(count_white)
print(count_blue)

해결 방법

graph의 [0][0]부터 다른 값이 나올 때까지 for문을 반복한다. 만약 다른 값이 나오면 check값을 -1로 바꾸고(-1 아니라 아무 값이나 가능) 반복문을 종료(break)한다. 

다른 값이 나온 시점 부터 2등분을 하며(n//=2) 각각 사분면에 재귀 함수를 사용하여 분할을 한다.

마지막으로 파란색(1), 흰색(0)으로 변환된 숫자를 카운트하며 해당 값을 출력한다.