알고리즘/백준[baekjoon]

[baekjoon] 백준 2630번 : 색종이 만들기 (with python) 재귀

코딩하는이씨 2022. 5. 29. 19:38
728x90
반응형

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

 

2630번: 색종이 만들기

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

www.acmicpc.net

 

정답 code

#색종이 만들기
import sys
input = sys.stdin.readline

n = int(input())
paper = [list(map(int,input().split())) for _ in range(n)]

result = []

def solution (x,y,n):
    color = paper[x][y]
    for i in range(x,x+n):
        for j in range(y , y+n):
            if color != paper[i][j]:
                solution(x,y,n//2)
                solution(x,y + n//2,n//2)
                solution(x+n//2 , y, n//2)
                solution(x+n//2, y+n//2, n//2)
                return
    if color == 0:
        result.append(0)
    else:
        result.append(1)

solution(0,0,n)
print(result.count(0))
print(result.count(1))

 

이번문제는 최근에 풀었던 1992번 과 상당히 유사한 문제다. 물론 더 전에도 자주 봤던 문제라 기억을 더듬어 해결 할수 있었다.

 

solution

재귀를 이용해 해당 종이에 다른 색이 있으면 종이를 쪼개 나가며 탐색하면 된다.

 

728x90
반응형