BAEKJOON : 2630, 1992

No. 2630

1. Problem

2. My Solution

• 재귀호출 종료조건
  - N = 1 인경우
  - N x N 종이가 모두 같은 색인 경우

• 하나의 종이 문제가 4개의 종이문제로 나뉨 (4개의 재귀호출)

import sys

def color_check(x,y,N):
    
    color = paper[x][y]

    for i in range(x,x+N):
        for j in range(y,y+N):
            if paper[i][j] != color:
                return True
    
    return False


def recursion(x,y,N):

    if N == 1:
        result[paper[x][y]] += 1
        return
    
    if color_check(x,y,N):
        recursion(x,y,N//2)
        recursion(x+N//2,y,N//2)
        recursion(x,y+N//2,N//2)
        recursion(x+N//2,y+N//2,N//2)
    else:
        result[paper[x][y]] += 1


n = int(sys.stdin.readline())
paper = [ list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
result = [0,0]  # result[0] = white, result[1] = blue

recursion(0,0,n)
print(result[0])
print(result[1])

3. Learned

• 재귀호출 문제를 풀 때, 종료조건이 꼭 하나가 아닐 수가 있음

---

No. 1992

1. Problem

2. My Solution

• 쿼드트리 개념의 문제 (위 문제 (2630) 와 동일한 원리)
• 재귀를 수행할 때 "(" 출력, 재귀를 완료하면 ")" 출력

import sys

def color_check(x,y,N):
    tmp = img[x][y]
    for i in range(x,x+N):
        for j in range(y,y+N):
            if tmp == img[i][j]:
                continue
            return False
    return True


def recursion(x,y,N):
    if N == 1:
        print(img[x][y], end='')
    elif color_check(x,y,N):
        print(img[x][y], end='')
    else:
        print("(",end='')
        recursion(x,y,N//2)
        recursion(x,y+N//2,N//2)
        recursion(x+N//2,y,N//2)
        recursion(x+N//2,y+N//2,N//2)
        print(")",end='')


n = int(sys.stdin.readline())
img = [ list(map(int,list(sys.stdin.readline().rstrip()))) for _ in range(n)]

recursion(0,0,n)

3. Learned

• 쿼드트리 (자식 노드를 4개 가지는 트리) 에 대해서 알게 됨