🎃 문제 설명

백준 2630 색종이 만들기

이 문제는 색종이를 자르는데 특정 구역이 같은 색깔이면 그만 잘라서 각 색깔 구간의 수를 구하는 분할정복 문제이다.

---

😏 사고 과정

가. 먼저 N이 8인경우를 그려본다.

나. 이중 for문을 돌려서 맨 처음 값과 비교하는 코드를 작성한다.

다. 만약 값이 서로 다를경우, 즉 8x8 배열의 모든 색깔값 (0또는1)이 다른 경우 어떻게 해야할지 생각한다.

[다. 에서 다를 경우]

1. 4등분으로 분할한다.
2. 각 분할에 대해 위의 가~다 부분을 한번더 적용한다 -> 분할정복이라는 것을 파악
3. 그렇다면 이중 for문에서 0~8이였는데 이것을 재귀함수로 만들기 위해서 8은 N으로 설정한다.
4. 그리고 각 4 분할 섹션들에 대해서 맨 왼쪽 좌표 기준으로 가~다를 실행한다.
	4.1 각 4분면의 왼쪽 좌표를 어떻게 구할까?
		-> (0,0), (0,4), (4,0), (4,4)
		=> (x,y), (x,4), (4,y), (4,4) 
	 
	 여기서 4는 8/2이다. 그리고 8은 (가)를 참고하면 8이였다. (in python, / -> //)
	 따라서, (x,y), (x,N/2), (N/2, y), (N/2, N/2)이다.  --- (i)
	 하지만, N/2가 0이라면 다음 N/2를 적용하지 못한다. 왜냐하면 0/2는 못하기 때문이다.(반례)
	 그래서, (x,y), (x,y+N/2), (x+N/2,y), (x+N/2, y+N/2)로 표현해야한다.
	 더불어, 위의 식이 좌표에서 직관적으로 가깝고 i식은 반례가 존재하기 때문에 사용할 수 없다.
	
	 
	 

라. 그리고 해당 섹션에서 for문을 무사히 돌려서 모든 인덱스값의 숫자(색깔)이 같을 때, 만약 1이면 result 리스트에 1을 추가하고 파란색 종이의 개수를 구하고 싶을 때 result에서 1의 개수를 찾으면 된다.

마. 전체 의사코드

dc(x,y,N): // 한 섹션에서 모든 인덱스의 값이 같은지 확인하는 함수가 된다.

	for x~x+N:
		for y~y+N:
			if 맨처음 인덱스 값(색깔) != mat[x][y] (같지 않다면) :
				dc(1번째 섹션 맨쪽위에 좌표, N//2) -> x,y
				dc 2번째                      -> x,y+N//2
				dc 3번째                      -> x+N//2, y
				dc 4번째                      -> x+N//2, y+N//2
				return (모두 다른 경우는 아래 if문에 못들어가게, 즉 모든 색깔이 같지 않으니까 이 섹션에 대한
				카운트는 해주지 않는 것이다.
	
	현재 섹션에서 모든 색깔이 같다면 일로 올것이다 위의 return을 안하니까
	if 맨처음게 1이면
		  result.append(1)
	else 0이면
			append(0)
				
			

---

🤐 전체코드, 결론 및 느낀점

# 플랫폼 : 백준
# 문제번호 : 2630
# 수준 : 실버2
# 알고리즘 : 분할정복

import sys
import os

# input = sys.stdin = open(os.getcwd() + "//5_Divide_and_Conquer//2630//input.txt", "r")
input=sys.stdin
N = int(input.readline())
mat = [list(map(int, input.readline().split())) for _ in range(N)]

# 0 : 하얀색
# 1 : 파란색

result = []

a
def dc(x, y, N, mat):
    color = mat[x][y]

    for i in range(x, x + N):
        for j in range(y, y + N):
            if color != mat[i][j]:
                dc(x, y, N // 2, mat)
                dc(x, y + N // 2, N // 2, mat)
                dc(x + N // 2, y, N // 2, mat)
                dc(x + N // 2, y + N // 2, N // 2, mat)
                return

    if color == 1:
        result.append(1)
    else:
        result.append(0)

def solution(N, mat):

    dc(0, 0, N, mat)
    print(result.count(0))
    print(result.count(1))

if __name__ == "__main__":
    solution(N, mat)

답 없이는 여전히 바로 떠올리기 힘들었고 계속 풀어서 익숙해져야겠다 라는 생각밖이 들지 않는다.