[분할 계획] 백준 Silver II 2630 색종이 만들기 (Python 파이썬)

💡문제 링크

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

💡문제 분석 요약

여러 개의 정사각형 칸으로 이루어진 정사각형 모양의 종이가 있다.

각 정사각형은 파란색(1) 혹은 흰색(0)

아래의 규칙에 따라 종이를 자른다.

1. 모두 같은 색으로 칠해져 있지 않으면 4등분으로 자르기

2. 모두 같은 색으로 칠해져있거나 하나의 정사각형 칸으로 이루어져 있어서 더 이상 4등분 할 수 없을 때까지 1을 반복

최종적으로 나누어진 하얀색 색종이의 개수, 파란색 색종이의 개수를 출력한다. 

 

💡알고리즘 설계

작은 문제를 통해 큰 문제를 해결하는 분할 정복 알고리즘을 사용하였다.

분할 정복 알고리즘은 1)분해 - 2)정복 - 3) 결합 이 세 과정으로 구성된다.

1) 분해: 문제를 4개로 나눈다.

2) 정복: 나눠진 부분에서 문제를 해결해서 결과를 얻는다.

3) 결합: 각 부분 결과를 합쳐서 답을 출력한다.

분할 정복 알고리즘이니까 재귀함수를 활용해야 한다.

재귀함수 함수(A, n) 구상

일단 함수 밖에서 파란색 색종이 개수와 하얀색 색종이 개수 blue, white = 0, 0으로 초기화
1. 모든 숫자가 1이면: blue += 1
2. 모든 숫자가 0이면: white +=1
3. 그 외: n을 n/2로 갱신하고, 색종이를 4등분으로 자른다
3-1. 1사분면에 대해 다시 재귀함수
3-2. 2사분면에 대해 다시 재귀함수
3-3. 3사분면에 대해 다시 재귀함수
3-4. 4사분면에 대해 다시 재귀함수

 

1~4분면을 나타내는 코드

[A[i][:n] for i in range(n)]
[A[i][n:] for i in range(n)]
[A[i][:n] for i in range(n, len(A))]
[A[i][n:] for i in range(n, len(A))]

 

의사 코드 짜보기

# 2차원 배열 속 숫자의 개수를 세는 count(matrix, number) 만들기

# 계속 반복해야하니까 재귀함수 division(A, n) 만들기 - 여기서 A는 2차원 배열, n은 len(A)

 

💡코드

# 색종이 배열 만들기
n = int(input())
color_paper = [list(map(int, input().split())) for _ in range(n)]
blue, white = 0, 0

# 2차원 배열 속 숫자 개수 세기
def count(matrix, number):
    count = 0
    for row in matrix:
        for element in row:
            if element == number:
                count += 1
    return count

# 분할 정복을 이용한 색종이 자르기
def devision(A, n):
    global blue, white
    c1, c0 = count(A, 1), count(A, 0)
    if c1 == len(A)**2:
        blue += 1
    elif c0 == len(A)**2:
        white += 1
    else:
        n = n // 2
        devision([A[i][:n] for i in range(n)], n)
        devision([A[i][n:] for i in range(n)], n)
        devision([A[i][:n] for i in range(n, len(A))], n)
        devision([A[i][n:] for i in range(n, len(A))], n)

# 실행
devision(color_paper, n)
print(white)
print(blue)

 

💡 오답 풀이

1. 처음에는 devision함수의 매개변수로 A만 넣었다. 그런데 생각해보니 애초에 첫 번째 줄에 input으로 n을 받아서, n도 매개변수로 넣었다. 

2. 처음에는 1) 전부 1이거나 0이면 2) 길이가 1이면 3) 그 외 - 이렇게 3단계로 나눠서 if문을 작성했는데,
생각해보니 2)의 케이스가 1)에 포함되었다.

 

💡 다른 풀이

k = int(input())
colored_paper = []

for _ in range(k):
  a = list(map(int, input().split()))
  colored_paper.append(a)

white = 0
blue = 0

def devide(x, y, n):
    global white, blue
    color = colored_paper[x][y] 

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != colored_paper[i][j]:
                devide(x, y, n // 2)                      
                devide(x, y + n // 2, n // 2)             
                devide(x + n // 2, y, n // 2)             
                devide(x + n // 2, y + n // 2, n // 2)    
                return

    if color == 0:
        white += 1
    else:
        blue += 1

devide(0, 0, k)
print(white, blue, sep='\n')

내 풀이와 다른 점 1: 재귀함수의 매개변수

나는 2차원 리스트랑 n만 넣었는데, 다른 풀이는 2차원 리스트 대신 x, y를 넣어서 2차원 리스트 내에서 어느 부분을 탐색할지 미리 정하였다.

내 풀이와 다른 점 2: 모두 같은 색인지 판단하는 방법

나는 모든 원소들 중에서 1의 개수가 리스트의 길이와 같은지 비교해서, 즉 개수를 비교해서 판단
다른 풀이는 탐색할 범위의 맨 왼쪽 위에 위치한 숫자(0 혹은 1)을 color라고 지정하고, 다른 원소들을 탐색하면서 다른 게 하나라도 발견되면 바로 4등분

개인적으로 다른 풀이가 더 깔끔해보이기는 한다..

 

💡 느낀점 or 기억할정보

위-내가 짠 코드 / 아래 - 다른 풀이

처음에는 막막했는데 작은 문제로 쪼개서 보니까 풀렸다.

앞으로 어떻게 알고리즘 문제를 해결해야할지 감을 잡아가는중