BAEKJOON : 2630, 1992


No. 2630


1. Problem

2. My Solution

  • 再帰呼び出し終了条件
    -N=1.
    -NxN用紙が同じ色の場合.

  • 1つの紙面問題を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サブノードツリー)
  • について