[백준] 2630번 : 색종이 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 색종이를 반으로 계속 자르면서 흰색 색종이와 파란색 색종이로 나누고 그 개수를 구하는 문제이다.

색종이를 반으로만 계속 잘라 새로운 정사각형 모양의 색종이를 계속 판단하며 완전한 흰색 색종이, 파란색 색종이를 구분한다.

이는 분할의 연장선으로 볼 수 있기 때문에 해당 문제를 분할 정복 알고리즘으로 해결할 수 있다.

해당 문제에서 중요한 점은 매번 색종이를 반으로 나누어 새로운 정사각형 모양의 색종이를 만드는 것과 새롭게 만들어진 색종이가 완전한 흰색 색종이인지, 파란색 색종이인지, 섞여 있는 색종이인지 판별하는 것이다.

하여 해당 중요한 2가지 부분을 각각 함수로 만들어 문제를 재귀적으로 해결하였다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 전체 종이의 한 변의 길이를 입력받는다. N = int(sys.stdin.readline())
3. 전체 종이를 2차원 리스트로 저장해 줄 빈 리스트를 생성한다. paper = []
4. 한 변의 길이만큼 반복하며 각 행별 정보를 리스트로 입력받아 전체 종이 리스트에 추가한다. for _ in range(N): paper.append(list(map(int, sys.stdin.readline().split())))
5. 해당 색종이가 어떤 색인지 판별하는 함수를 정의한다. def check(paper)
   1. 해당 색종이에 있는 흰색 칸의 개수를 저장할 변수를 생성하고 초기화한다. count_0 = 0
   2. 해당 색종이에 있는 파란색 칸의 개수를 저장할 변수를 생성하고 초기화한다. count_1 = 0
   3. 판별할 색종이의 각 행을 차례대로 불러와 for row in paper
      1. 각 행의 0의 개수를 세어 더해주고 count_0 += row.count(0)
      2. 1의 개수를 세어 더해준다. count_1 += row.count(1)
   4. 만약 흰색 칸의 개수가 0개이면 해당 종이는 완전한 파란색 색종이이므로 blue를 반환해 준다. if (count_0 == 0): return 'blue'
   5. 만약 파란색 칸의 개수가 0개이면 해당 종이는 완전한 흰색 색종이이므로 white를 반환해 준다. elif (count_1 == 0): return 'white'
   6. 반면에 두 색의 칸 개수가 모두 0이 아니면 해당 색종이는 흰색과 파란색이 섞여있는 색종이이므로 False를 반환해 준다. else: return False
6. 해당 색종이를 반으로 나누어 새로운 정사각형 색종이 4장을 만드는 함수를 정의한다. def divide(N, paper)
   1. 새로운 정사각형 색종이의 한 변의 길이를 저장한다. size = N // 2
   2. 색종이를 각 4 부분으로 잘라 저장한다. p_1 = [row[ : size] for row in paper[ : size]]
   3. p_2 = [row[size : ] for row in paper[ : size]]
   4. p_3 = [row[ : size] for row in paper[size : ]]
   5. p_4 = [row[size : ] for row in paper[size : ]]
   6. 자른 4개의 조각을 한 리스트로 묶어 저장해 둔다. new_paper = [p_1, p_2, p_3, p_4]
   7. 자른 4개의 조각을 각각 하나씩 불러오며 for p in new_paper
      1. 해당 색종이가 어떤 색으로 이루어졌는지 판별한다. result = check(p)
      2. 만약 해당 색종이가 완전한 파란색 색종이이면 파란색 색종이의 개수를 1 증가시킨다. if (result == 'blue'): answer[result] += 1
      3. 만약 해당 색종이가 완전한 흰색 색종이이면 흰색 색종이의 개수를 1 증가시킨다. elif (result == 'white'): answer[result] += 1
      4. 반면에 해당 색종이가 흰색과 파란색이 섞인 색종이라면 해당 색종이를 다시 나눈다. else: divide(size, p)
7. 각 파란색 색종이와 흰색 색종이의 개수를 저장해 줄 딕셔너리를 생성한다. answer = {'blue' : 0, 'white' : 0}
8. 처음 전체 종이가 완전한 파란색, 흰색 색종이일 수 있으므로 해당 종이의 색을 판별한다.
9. 만약 전체 종이의 색이 완전한 파란색이면 파란색 색종이의 개수를 1 증가시킨다. if (check(paper) == 'blue'): answer['blue'] += 1
10. 만약 전체 종이의 색이 완전한 흰색이면 흰색 색종이의 개수를 1 증가시킨다. elif (check(paper) == 'white'): answer['white'] += 1
11. 반면에 전체 종이가 흰색과 파란색이 섞인 색종이라면 해당 종이를 나눈다. else: divide(N, paper)
12. 최종 흰색 색종이의 개수를 출력한다. print(answer['white'])
13. 최종 파란색 색종이의 개수를 출력한다. print(answer['blue'])

3. 소스코드

import sys

N = int(sys.stdin.readline())
paper = []
for _ in range(N):
    paper.append(list(map(int, sys.stdin.readline().split())))

def check(paper):
    count_0 = 0
    count_1 = 0

    for row in paper:
        count_0 += row.count(0)
        count_1 += row.count(1)

    if (count_0 == 0):
        return 'blue'
    elif (count_1 == 0):
        return 'white'
    else:
        return False

def divide(N, paper):
    size = N // 2

    p_1 = [row[ : size] for row in paper[ : size]]
    p_2 = [row[size : ] for row in paper[ : size]]
    p_3 = [row[ : size] for row in paper[size : ]]
    p_4 = [row[size : ] for row in paper[size : ]]

    new_paper = [p_1, p_2, p_3, p_4]

    for p in new_paper:
        result = check(p)
        if (result == 'blue'):
            answer[result] += 1
        elif (result == 'white'):
            answer[result] += 1
        else:
            divide(size, p)

answer = {'blue' : 0, 'white' : 0}
if (check(paper) == 'blue'):
    answer['blue'] += 1
elif (check(paper) == 'white'):
    answer['white'] += 1
else:
    divide(N, paper)

print(answer['white'])
print(answer['blue'])