[백준 2630 번] 색종이 만들기 | python 풀이

---

 

 📝백준 2630

✂️색종이 만들기

💡 분할 정복, 재귀

 

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

 

---

 

 

백준 2630번 채점 결과

 

 

 

🔷 Submission Code

## 백준
## 2630번 : 색종이 만들기
## 분할 정복, 재귀

##* 문제 규칙
## 모두 같은 색으로 칠해져 있지 않으면 중간 부분 자름
## 종료 조건 : 모두 같은색, 하나의 정사각형 될경우
## 하얀색 0, 파란색 1
## 출력 첫째줄 : 하얀색 색종이 개수, 둘째줄 : 파란색 색종이 개수


def makepaper(x, y, N):
    global wCount, bCount
    color = paper[x][y]
    
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != paper[i][j]:
                makepaper(x, y, N//2)
                makepaper(x, y+N//2, N//2)
                makepaper(x+N//2, y, N//2)
                makepaper(x+N//2, y+N//2, N//2)
                return

    if color == 0:
        wCount +=1
    else:
        bCount +=1

if __name__ == "__main__":
    N = int(input())  # N : 한변의 길이 ( N=2k, k는 1 이상 7 이하의 자연수 )
    paper = [list(map(int, input().split())) for _ in range(N)]
    wCount, bCount = 0, 0

    makepaper(0,0,N)
    print(wCount)
    print(bCount)

 

 

백준 2630번 색종이 만들기는 분할 정복을 적용하여 풀 수 있는 문제이다. 종이의 색이 같지 않을 경우 중간 부분에 자르는 작업을 반복적으로 해주게 된다. 이러한 함수는 재귀 함수를 통해서 동작시킬 수 있다. 종이의 색이 모두 같은 색으로 칠해져 있거나 하나의 정사각형이 될 때까지 작업을 반복해준다. 그리고 마지막에 나누어진 색종이 개수를 출력해주는 문제이다.

 

 

 

 

색종이 쪼개지는 예시 그림

 

 

 

---

 

 

 

 

 

🔶 main 코드

##* 문제 규칙
## 모두 같은 색으로 칠해져 있지 않으면 중간 부분 자름
## 종료 조건 : 모두 같은색, 하나의 정사각형 될경우
## 하얀색 0, 파란색 1
## 출력 첫째줄 : 하얀색 색종이 개수, 둘째줄 : 파란색 색종이 개수

##* 코드 전체적인 흐름
if __name__ == "__main__":
    N = int(input())  # N : 한변의 길이 ( N=2k, k는 1 이상 7 이하의 자연수 )
    paper = [list(map(int, input().split())) for _ in range(N)]
    wCount, bCount = 0, 0

    makepaper(0,0,N)
    print(wCount)
    print(bCount)

첫번째 입력값으로 한 변의 길이를 입력받아서 N 변수에 저장해준다. 그리고 N 만큼 for문과 list comprehension으로 종이의 색 값인 0과 1 값을 paper 변수에 저장한다. 흰색 종이와 파란색 색종이 개수를 0으로 초기화를 해주고 색종이 반으로 나누면서 종이를 만들어 주는 함수인 makepaper를 거친 후 색종이 개수를 출력해준다.

 

 

 

 

---

 

 

 

 

🔶 makepaper 함수

def makepaper(x, y, N):
    global wCount, bCount
    color = paper[x][y]
    
    for i in range(x, x+N):
        for j in range(y, y+N):
            if color != paper[i][j]:
                makepaper(x, y, N//2)
                makepaper(x, y+N//2, N//2)
                makepaper(x+N//2, y, N//2)
                makepaper(x+N//2, y+N//2, N//2)
                return

    if color == 0:
        wCount +=1
    else:
        bCount +=1

처음에 x,y 매개변수로 0이 들어온다. 먼저 color 변수에 종이 가장자리 부분 색깔을 넣어준다. 이중 for문을 돌면서 i과 j로 paper의 행, 열 인덱스를 접근하면서 해당 인덱스의 좌표 색깔이 아까 저장해놓은 가장자리 색과 같은지 비교하고 다를 경우 종이 가로 세로 쪼개기를 해준다. 종이를 4등분으로 쪼개는 거는 재귀 함수를 통해서 동작이 되며 재귀 함수의 종료 조건이 될 때까지 반복하게 된다. makepaper 마지막에는 조건문을 통해서 종이 색깔 global 변수를 증가시켜준다.

 

 

 

 

 

 

 

 

 

 

소스 코드 링크 : 

https://github.com/KwanHoo/Data-Structure__Algorithm/blob/main/Python/baekjoon/silver/Baek_2630.py

GitHub - KwanHoo/Data-Structure__Algorithm: Data structures and algorithms practice code, Backjoon submission code