[Baekjoon]백준 2630 색종이 만들기(실버 2) - Python

문제설명 1

문제설명 2

문제를 살펴보면 각 정사각형(사이즈는 2^0, 2^1....) 안에 하나의 색깔만 존재하도록 하는 경우를 찾아

그 정사각형의 색이 하얀색인 경우와 파란색인 경우를 각 줄마다 출력하는 문제이다

해당 문제를 풀기위해서 재귀함수를 사용하는 방법을 생각하였다 만약 정사각형 안을 확인하다가

다른 색깔이 등장하면 그 정사각형에서 size별로 다시 나누어야하기 때문이다

 

그래서 특정 사각형의 제일 첫번째 위치의 색깔을 기준으로 삼고, for문을 통해 전체 정사각형의 색깔을 확인

하는 로직을 작성하였다 이후에 if문을 통해서 색이 다른 경우를 찾게되고, 만약 그러한 경우를 찾게 된다면

재귀적으로 함수를 호출하되, size는 2로 나눈 값을 넣어주고 x, y는 새로운 size에 맞게 이동하여주면 된다

sol(x, y, size // 2)                            # 1사분면
sol(x, y + size // 2, size // 2)                # 2사분면
sol(x + size // 2, y, size // 2)                # 3사분면
sol(x + size // 2, y + size // 2, size // 2)    # 4사분면

이후 기준점의 색깔이 하얀색인 경우와 파란색인 경우로 나누어 +1을 해준 값을 전역변수에 저장하면 된다

그리고 제일 처음 확인하는 기준은 0, 0이고, size는 입력받은 값이므로 이를 함수에 넣어주면 된다

def sol(x, y, size):
    global white, blue
    color = square[x][y] # 기준
    for i in range(x, x + size):
        for j in range(y, y + size):
            if color != square[i][j]: # 색이 다른 경우
                sol(x, y, size // 2)                            # 1사분면
                sol(x, y + size // 2, size // 2)                # 2사분면
                sol(x + size // 2, y, size // 2)                # 3사분면
                sol(x + size // 2, y + size // 2, size // 2)    # 4사분면
                return
    if color == 0:
        white += 1
    else:
        blue += 1
                
size = int(input())
square = []
white, blue = 0, 0
for _ in range(size):
    square.append(list(map(int, input().split())))
    
sol(0, 0, size)
print(white)
print(blue)