[algorithm] 백준 2630 - 색종이 만들기

[algorithm] 백준 2630 - 색종이 만들기

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 2630번 문제 - 색종이 만들기 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 2630

 

백준 2630번 색종이 만들기 문제 보러가기

 

반응형

 

문제 해석

 

색종이의 색이 다른 부분이 존재하면 영역을 나눠가면서 잘라나가는 과정을 정사각형모양으로 색이 모두

같을 때까지 진행하고 결과로 나온 색종이의 색깔별 개수를 파악하면 되는 문제입니다.

힌트 : 같은 작업을 적용시키기 위해서 재귀를 사용해줍시다.

 

풀이

 

# 2630 색종이 만들기

import sys

def f(x, y, N):
  paper_color = square[x][y]
  for i in range(x, x + N):
    for j in range(y, y + N):
      if paper_color != square[i][j]:
        f(x, y, N//2)
        f(x, y + N//2, N//2)
        f(x + N//2, y, N//2)
        f(x + N//2, y + N//2, N//2)
        return
  if paper_color == 0:
    color_list.append(0)
  else:
    color_list.append(1)
    
N = int(sys.stdin.readline())
square = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] 

color_list = []

f(0, 0, N) # 함수 호출

print(color_list.count(0))
print(color_list.count(1))

 

풀이 해석 및 팁

 

문제에서 재귀함수로 사용되는 f함수 안에서 검사하는 곳이 기준점과 색이 다를 경우 종이를 자르는 것과 같은

동작이 f함수를 안에서 다시 호출하는 것입니다.

N의 크기를 작게 설정하고 디버그 모드에서 한 줄씩 실행해보면서 어떤식으로 동작하는지를 살펴보면

쉽게 이해가 가실겁니다.

---

여기까지 백준 2630번 색종이 만들기 문제 풀이였습니다.

이번 문제의 정답률은 69% 정도입니다.

 

많은 분들이 어려움 없이 해결한 문제였습니다.

 

어제가 어버이날이었는데 여러분들은 부모님과 좋은 시간 보내셨나요??

 

꼭 어버이날이 아니더라도 가끔 가족들과 함께하는 시간을 가지기위해 노력해봅시다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.