[2630] 색종이 만들기

2023-04-19 | Algorithms / 백준 문제 풀이 모음 # Python, Sliver 2

백준 문제 풀이

문제 링크

2630번: 색종이 만들기

• 해설

    종이의 색깔이 지정되어있고, 정사각형 모양으로 4등분해서 같은 색 종이로만 분해하는 것이 목적이고, 각 색깔별로 개수를 출력해야한다.
    종이의 개수는 하얀색 W, 파란색 B에 담는다.
      
    큰 종이가 있는 상태에서 4조각으로 나누어서 색이 다른 경우에는 다시 쪼개는 패턴이 있다.
    그러면 생각해야되는 부분이 종이의 색이 다른가? 를 체크하는 방식인데..
      
    정말 다행이도 N이 2, 4, 8, 16, 32, 64, 128 중 하나라고 나타나있어서 최대 128일때 이중 for문을 이용해서
    각 종이의 색을 일일히 체크하는 방식으로 해도 시간초과가 걸리지 않을 것이다.
      
    방법은 단순하다.
      
    1.왼쪽 위 좌표와 오른쪽 아래 좌표를 받는 diff_color 라는 함수를 작성한다.
    	- 해당 함수에서는 좌표 사이에 색이 다른 것이 있는지 체크한다.
      
    def diff_color(x1, y1, x2, y2):
        color = papers[x1][y1]
        is_same = True
        for i in range(x1, x2):
            for j in range(y1, y2):
                if color != papers[i][j]:
                    is_same = False
                    break
      
    2. 만약 해당 범위의 색이 같으면 True를 반환하는데, True 일때 해당 종의의 색 카운트를 +1 한다.
    	if is_same:
            if color == 0:
                W += 1
            else:
                B += 1
            return
      
    3. 색이 다른 경우... 4조각으로 나누어야 하는데, 단순히 search 를 4조각의 범위에 맞게 호출하면 된다.
        else:
            diff_color(x1, y1, (x1 + x2) // 2, (y1 + y2) // 2)
            diff_color(x1, (y1 + y2) // 2, (x1 + x2) // 2, y2)
            diff_color((x1 + x2) // 2, y1, x2, (y1 + y2) // 2)
            diff_color((x1 + x2) // 2, (y1 + y2) // 2, x2, y2)
      
    여기서 문제는 DP가 되는데 4조각으로 나눌수 없을때까지 나눌 수 있기 때문에 나눌 수 없을때 값을 반환해주어야 한다.
    나눌 수 없다는 것은 한변의 길이가 1이면 나눌수 없기 때문에 해당 조건을 추가해준다.
    	if abs(x2 - x1) == 1:
            if color == 0:
                W += 1
            else:
                B += 1
            return
      
    이러면 DP로 한변의 길이가 1일때 해당 종이의 숫자를 +1 해서 return 하기 때문에 가장 작은 종의의 수까지 DP 스택이 된다.
    여기까지 오면, 같은 색의 가장 작은 단위의 종이까지 탐색하게 되어서 모든 색 종이의 수를 각각 출력할 수 있다.
      
  

• 답안

    import sys
      
    def diff_color(x1, y1, x2, y2):
        color = papers[x1][y1]
        global W
        global B
        if abs(x2 - x1) == 1:
            if color == 0:
                W += 1
            else:
                B += 1
            return
      
        is_same = True
        for i in range(x1, x2):
            for j in range(y1, y2):
                if color != papers[i][j]:
                    is_same = False
                    break
      
        if is_same:
            if color == 0:
                W += 1
            else:
                B += 1
            return
        else:
            diff_color(x1, y1, (x1 + x2) // 2, (y1 + y2) // 2)
            diff_color(x1, (y1 + y2) // 2, (x1 + x2) // 2, y2)
            diff_color((x1 + x2) // 2, y1, x2, (y1 + y2) // 2)
            diff_color((x1 + x2) // 2, (y1 + y2) // 2, x2, y2)
      
    if __name__ == "__main__":
        N = int(sys.stdin.readline())
        papers = list()
        W = 0
        B = 0
        for i in range(N):
            colors = list(map(int, sys.stdin.readline().split()))
            papers.append(colors)
      
        diff_color(0, 0, N, N)
      
        print(W)
        print(B)