-
[항해99]알고리즘_07sparta/알고리즘 2021. 6. 22. 01:02
[Python] 백준 2630 색종이 만들기
문제분석
# 분할정복(Divide and Conquer)
- 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법
- 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식
# 한변의 길이 n을 입력값을 받고
# 변수를 하나 선언해서 두번째 입력값(각 색종이들의 숫자)을 리스트 형식으로 받는다.(이중리스트)
# 각 종이를 확인하여 0이나 1만 가지고 있는 색종이 발견시 추가할 리스트(result)를 초기화 한다.
# 재귀함수를 이용해 반복문을 돌면서 시작점과 x,y,n까지의 숫자를 비교했을 때 같은지 확인한다.
# 시작점과 반복문으로 돈 입력값의 숫자가 같다면, 초기화 한 result 리스트에 append 한다.
# 시작점과 반복문으로 돈 입력값의 숫자가 다르다면, 분할 후 한면씩 반복문을 돈다.
# 반복문을 돌리면서 전체 색이 같아지는 순간에 초기화 한 result 리스트에 append 한다.
4분할 후 분할된 면 중에 첫 면 먼저 해결/ 여기서도 해결 안되면 더 작게 4분할 하고 다시 그 분할면 중에 첫 면 먼저 해결될때까지 반복문 돌림. 문제풀이
import sys N = int(sys.stdin.readline()) paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # [[1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1]] result = [] # 0이나 1만 가지고 있는 색종이 생기면 추가 def solution(x, y, N): num = paper[x][y] # 변수에 각 정사각형 종이의 자리 할당 / paper[0][0] = 1 for i in range(x, x+N): # 시작점과 숫자가 같은지 반복문을 돌면서 확인 for j in range(y, y+N): if num != paper[i][j]: # 숫자가 다르면 4분할 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 num == 0: result.append(0) else: # color == 1 result.append(1) solution(0,0,N) print(result.count(0)) # result의 0의 개수 -> 하얀 종이 개수 print(result.count(1)) # result의 1의 개수 -> 파란 종이 개수
'sparta > 알고리즘' 카테고리의 다른 글
[항해99]알고리즘_08 (0) 2021.06.22 [항해99]알고리즘_06 (0) 2021.06.21 [항해99]알고리즘_05 (0) 2021.06.20 [항해99]알고리즘_04 (0) 2021.06.18 [항해99]알고리즘_03 (0) 2021.06.17