2630. 색종이 만들기
by 브이담곰
https://www.acmicpc.net/problem/2630
✔ 유형 : 이분 탐색
✔ 문제 풀이: 큰 문제를 작은 문제로 분할하여 작은 문제부터 순차적으로 해결한 뒤 결과를 합한다.
탐색할 영역의 제일 왼쪽 위의 색을 저장해두고, 이중 for문으로 다른 색이 포함되어 있는지 확인한다.
만약 다른 색이 포함되어있다면 각 면을 N/2로 나눠서 총 4 부분으로 나눈다.
계속 나누다가 언젠간 한면이 1이되면 해당 색을 배열에 저장한다. 만약 한 구역을 검사했는데 모두 같은 색이라면 해당 색을 배열에 저장한 후 함수를 리턴한다.
위의 방법을 아래의 코드로 나타내었다.
import sys
input=sys.stdin.readline # input함수 바꾸기
import copy
#input
N = int(input()) # 종이의 크기
W=[[*map(int,input().split())] for _ in range(N)] # 정리 해두기 N행 배열 입력 받는 법
result = []
#크기가 4씩 나눠짐.
def divided_conquer(div, start): # start = {x,y}
color = W[start[0]][start[1]]
for i in range(start[0], start[0] + div):
for j in range(start[1], start[1]+div):
if color != W[i][j]:
# 만약 다른 색이 나온다면 분할한다.
divided_conquer(div//2, start)
divided_conquer(div//2, [start[0], start[1]+ div//2 ])
divided_conquer(div//2, [start[0]+ div//2 , start[1]])
divided_conquer(div//2, [start[0]+ div//2 , start[1]+ div//2 ])
return
if color == 0:
result.append(0)
else:
result.append(1)
return
divided_conquer(N, [0,0])
print(result.count(0))
print(result.count(1))
'Coding Test > Baekjoon' 카테고리의 다른 글
1197. 최소 스패닝 트리 (0) | 2024.07.18 |
---|---|
5639. 이진 검색 트리 (0) | 2024.07.18 |
2805. 나무 자르기 (0) | 2024.07.11 |
3109. 뱀 (0) | 2024.07.10 |
2493. 탑 (0) | 2024.07.10 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰