[백준] 1780번 : 종이의 개수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 -1, 0, 1로 이루어진 종이를 가로로 3등분, 세로로 3등분 총 9개의 조각으로 나누며 총 -1, 0, 1로만 이루어진 종이의 개수를 구하는 문제이다.

해당 종이가 -1, 0, 1의 숫자 중에서 어떻게 구성되어 있는지 판단하고 만약 각각 -1, 0, 1로만 이루어진 종이라면 각 -1, 0, 1의 종이의 개수를 세어준다.

반면에 해당 종이가 -1, 0, 1의 숫자 중 두 가지 이상의 숫자로 이루어진 종이라면 다시 9개의 조각으로 나누어 다시 판별하고 해당 종이의 개수를 세어준다.

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

종이가 어떤 숫자로 구성되어 있는지 판별하는 함수와 종이를 9개의 조각으로 나누는 함수를 재귀적으로 사용하여 문제를 해결한다.

종이를 9개로 나누는 부분을 중요하게 살펴보면 아래 조각으로 나눌 수 있다.

p_1 = [row[size * 0 : size * 1] for row in paper[size * 0 : size * 1]]
p_2 = [row[size * 1 : size * 2] for row in paper[size * 0 : size * 1]]
p_3 = [row[size * 2 : size * 3] for row in paper[size * 0 : size * 1]]

P_4 = [row[size * 0 : size * 1] for row in paper[size * 1 : size * 2]]
p_5 = [row[size * 1 : size * 2] for row in paper[size * 1 : size * 2]]
p_6 = [row[size * 2 : size * 3] for row in paper[size * 1 : size * 2]]

p_7 = [row[size * 0 : size * 1] for row in paper[size * 2 : size * 3]]
p_8 = [row[size * 1 : size * 2] for row in paper[size * 2 : size * 3]]
p_9 = [row[size * 2 : size * 3] for row in paper[size * 2 : size * 3]]

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 종이의 크기를 입력받는다. N = int(sys.stdin.readline())
3. 종이의 구성을 저장하기 위한 리스트를 생성한다. paper = []
4. 종이의 크기만큼 반복하며 for _ in range(N)
   1. 한 줄씩 입력받아 리스트로 저장하고 li = list(map(int, sys.stdin.readline().split()))
   2. 이를 종이의 구성 리스트에 추가한다. paper.append(li)
5. 종이의 구성을 판별할 함수를 생성한다. def check(paper)
   1. -1의 개수를 저장할 변수를 생성하고 초기화한다. count__1 = 0
   2. 0의 개수를 저장할 변수를 생성하고 초기화한다. count_0 = 0
   3. 1의 개수를 저장할 변수를 생성하고 초기화한다. count_1 = 0
   4. 판별할 종이를 한 줄씩 불러오며 for p in paper
      1. -1의 개수를 세어 -1의 개수를 저장하는 변수에 더해준다. count__1 += p.count(-1)
      2. 0의 개수를 세어 0의 개수를 저장하는 변수에 더해준다. count_0 += p.count(0)
      3. 1의 개수를 세어 1의 개수를 저장하는 변수에 더해준다. count_1 += p.count(1)
   5. 만약 0의 개수와 1의 개수가 모두 0이면(-1로만 이루어진 종이이면) '-1'을 반환해 준다. if (count_0 == 0) and (count_1 == 0): return '-1'
   6. 만약 -1의 개수와 1의 개수가 모두 0이면(0으로만 이루어진 종이이면) '0'을 반환해 준다. elif (count__1 == 0) and (count_1 == 0): return '0'
   7. 만약 -1의 개수와 0의 개수가 모두 0이면(1로만 이루어진 종이이면) '1'을 반환해 준다. elif (count__1 == 0) and (count_0 == 0): return '1'
   8. 모두 아니라면(-1, 0, 1 중 2가지 이상의 숫자가 섞여있는 종이이면) False를 반환해 준다. else: return False
6. 종이를 9개의 조각으로 나누어 각 종이를 판별하는 함수를 생성한다. def divide(N, paper)
   1. 나누어질 조각의 크기를 저장한다. size = N // 3
   2. 새롭게 나누어질 종이들을 저장할 리스트를 생성한다. new_paper = []
   3. 각 가로로 3등분, 세로로 3등분을 하며 for i in range(3): for j in range(3)
      1. 새롭게 종이를 나누고 p = [row[size * j : size * (j + 1)] for row in paper[size * i : size * (i + 1)]]
      2. 나눈 종이를 새 종이 리스트에 추가한다. new_paper.append(p)
   4. 나눈 9개의 새로운 종이를 하나씩 불러오며 for np in new_paper
      1. 해당 종이의 구성을 판별하고 result = check(np)
      2. 만약 해당 종이가 섞여있는 종이라면 해당 종이를 다시 9개로 나누어 판별한다. if (not result): divide(size, np)
      3. 반면에 해당 종이가 한 가지 색으로 이루어진 종이라면 해당 종이의 개수를 1 증가시켜 준다. else: answer[result] += 1
7. 각 종이의 개수를 저장할 딕셔너리를 생성한다. answer = {'-1' : 0, '0' : 0, '1' : 0}
8. 처음 종이의 구성을 판별한다. result = check(paper)
9. 만약 해당 종이가 섞여있는 종이라면 해당 종이를 다시 9개로 나누어 판별한다. if (not result): divide(N, paper)
10. 반면에 해당 종이가 한 가지 색으로 이루어진 종이라면 해당 종이의 개수를 1 증가시켜 준다. else: answer[result] += 1
11. 모든 종이에 대한 판별이 끝나면 -1 종이의 개수를 출력하고 print(answer['-1'])
12. 0 종이의 개수를 출력하고 print(answer['0'])
13. 1 종이의 개수를 출력한다. print(answer['1'])

3. 소스코드

import sys

N = int(sys.stdin.readline())

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

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

    for p in paper:
        count__1 += p.count(-1)
        count_0 += p.count(0)
        count_1 += p.count(1)

    if (count_0 == 0) and (count_1 == 0):
        return '-1'
    elif (count__1 == 0) and (count_1 == 0):
        return '0'
    elif (count__1 == 0) and (count_0 == 0):
        return '1'
    else:
        return False

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

    new_paper = []
    for i in range(3):
        for j in range(3):
            p = [row[size * j : size * (j + 1)] for row in paper[size * i : size * (i + 1)]]
            new_paper.append(p)

    for np in new_paper:
        result = check(np)
        if (not result):
            divide(size, np)
        else:
            answer[result] += 1

answer = {'-1' : 0, '0' : 0, '1' : 0}
result = check(paper)
if (not result):
    divide(N, paper)
else:
    answer[result] += 1

print(answer['-1'])
print(answer['0'])
print(answer['1'])