[백준/Python] (S2) 2630 - 색종이 만들기

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

색종이 만들기 성공

 

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

46826

32646

25147

69.630%

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

예제 출력 1 복사

9
7

---

분할 정복과 재귀함수를 사용해 풀면된다.

 

일단 처음에 들어오는 배열을 살펴보자

이것을 4 * 4 사이즈의 종이로 잘라서 다시 비교를 해야한다.

즉, 한번 자를때마다 n / 2 크기의 종이로 잘리게 된다.

이후, 1 * 1 크기의 종이일때는 더이상 자르지 않아도 되고 종이의 색깔만 판별해주면 된다.

 

이 문제의 핵심은 "종이를 어떻게 자를것인가?" 이다.

 

파이썬에서는 쉽게 슬라이싱 연산을 지원한다. numpy라이브러리를 사용하면 쉽게 2차원 배열의 슬라이싱을 진행할 수 있지만, 백준에서는 numpy라이브러리를 지원하지 않는다. 따라서 슬라이싱 연산을 따로 구현해주어야 한다.

def check(n,p): #가로, 세로 나눈 리스트의 배열이 들어간다.
    ~~중략~~
            
        else: #두 케이스가 아니라면 다른 색깔이 섞여있는것. 나눠야함.
            arr = []
            for i in range(n // 2): #좌상
                arr.append(p[i][0:n//2])
                
            for i in range(n // 2): #우상
                arr.append(p[i][n//2 :n])

            for i in range(n // 2,n): #좌하
                arr.append(p[i][0:n//2])
                
            for i in range(n // 2,n): #우하
                arr.append(p[i][n//2 :n])
                
            for i in range(0, len(arr), n//2):
                check(n//2,list(arr[i:i+n//2]))

이런식으로 좌상, 우상, 좌하, 우하 네 구역을 나눠서 자른 값을 배열에 저장한 후, 마지막으로 반복문을 한번 더 진행해서 종이 크기만큼 묶음으로 다시 리스트에 넘겨줬다.

이러한 작업을 거치면 묶음으로 리스트에 넘겨줄 때, 정 사각형이 된다.

 

그리고 받은 배열을 다시 함수를 호출해 넘겨주고, 넘겨받은 배열로 배열에 자를 부분이 있는지 검사하는 코드를 작성하였다.

def check(n,p): #가로, 세로 나눈 리스트의 배열이 들어간다.

    if n == 1: #더이상 나눌 수 없음
        if p[0] == [0]:
            white += 1
        else:
            blue += 1
        return
            
    else: #아니라면 일단 체크
        for i in range(n):
            for j in range(n):
                if p[i][j] == 1: #1로 색칠되어 있다면
                    count += 1 #카운트 증가
                
        #반복문을 빠져나온 후, count가 0 혹은 r*c 의 값과 동일하다면 같은색으로 채워져 있는것.
        if count == 0:
            white += 1
            return
            
        elif count == n**2:
            blue += 1
            return 
           
        ~~중략~~

직전의 코드에서 check 함수를 호출할 때, 첫 번째 매개변수로 받은 n의 값의 절반을 넘겨주고 있다. 

몫 연산자를 사용했지만, n이 1인경우엔 더이상 자를 수 없기 때문에 1일때는 바로 검사를 진행한다.

n이 1이 아닌경우에는 모든 색칠한 칸의 값을 더한다. count에 저장을 하는데 이때, 1은 파란색이고, 0은 하얀색이라고 했다.

색종이가 파란색이라면 n*n과 count가 같아질것이고, 하얀색이라면 0과 count가 같아질것이다. 만약 같지 않다면 그 종이는 한번 더 자를 수 있는 상태라는것이다.

 

이러한 방식으로 문제를 풀었고, 전체 코드는 다음과 같다.

#2630 색종이 만들기
white = 0
blue = 0 #색종이 갯수를 저장할 변수 두개

def check(n,p): #가로, 세로 나눈 리스트의 배열이 들어간다.
    count = 0 #나눈 색종이가 0인지 1인지 검사할 카운트
    global blue
    global white

    if n == 1: #더이상 나눌 수 없음
        if p[0] == [0]:
            white += 1
        else:
            blue += 1
        return
            
    else: #아니라면 일단 체크
        for i in range(n):
            for j in range(n):
                if p[i][j] == 1: #1로 색칠되어 있다면
                    count += 1 #카운트 증가
                
        #반복문을 빠져나온 후, count가 0 혹은 r*c 의 값과 동일하다면 같은색으로 채워져 있는것.
        if count == 0:
            white += 1
            return
            
        elif count == n**2:
            blue += 1
            return 
            
        else: #두 케이스가 아니라면 다른 색깔이 섞여있는것. 나눠야함.
            arr = []
            for i in range(n // 2): #좌상
                arr.append(p[i][0:n//2])
                
            for i in range(n // 2): #우상
                arr.append(p[i][n//2 :n])

            for i in range(n // 2,n): #좌하
                arr.append(p[i][0:n//2])
                
            for i in range(n // 2,n): #우하
                arr.append(p[i][n//2 :n])
                
            for i in range(0, len(arr), n//2):
                check(n//2,list(arr[i:i+n//2]))
            
n = int(input()) #값 입력받기
paper = [] #종이를 입력받을 빈 배열

for i in range(n): #종이 입력받기
    paper.append(list(map(int,input().split())))
    
check(n,paper) #체크 시작

print(white)
print(blue)