ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [항해99]알고리즘_07
    sparta/알고리즘 2021. 6. 22. 01:02

    [Python] 백준 2630 색종이 만들기

       문제분석   

    # 분할정복(Divide and Conquer)

      - 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법

      - 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄여가는 방식

    # 한변의 길이 n을 입력값을 받고

    # 변수를 하나 선언해서 두번째 입력값(각 색종이들의 숫자)을 리스트 형식으로 받는다.(이중리스트)

    # 각 종이를 확인하여 0이나 1만 가지고 있는 색종이 발견시 추가할 리스트(result)를 초기화 한다.

    # 재귀함수를 이용해 반복문을 돌면서 시작점과 x,y,n까지의 숫자를 비교했을 때 같은지 확인한다.

    # 시작점과 반복문으로 돈 입력값의 숫자가 같다면, 초기화 한 result 리스트에 append 한다.

    # 시작점과 반복문으로 돈 입력값의 숫자가 다르다면, 분할 후 한면씩 반복문을 돈다.

    # 반복문을 돌리면서 전체 색이 같아지는 순간에 초기화 한 result 리스트에 append 한다.

    4분할 후

     

    분할된 면 중에 첫 면 먼저 해결/ 여기서도 해결 안되면

     

    더 작게 4분할 하고 다시 그 분할면 중에 첫 면 먼저 해결될때까지 반복문 돌림.

     

       문제풀이   

    import sys
    
    N = int(sys.stdin.readline())
    paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    # [[1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 1]]
    result = []     # 0이나 1만 가지고 있는 색종이 생기면 추가
    
    def solution(x, y, N):
      num = paper[x][y]   # 변수에 각 정사각형 종이의 자리 할당 / paper[0][0] = 1
      for i in range(x, x+N):  # 시작점과 숫자가 같은지 반복문을 돌면서 확인
        for j in range(y, y+N):
          if num != paper[i][j]:  # 숫자가 다르면 4분할
            solution(x, y, N//2)
            solution(x, y+N//2, N//2)
            solution(x+N//2, y, N//2)
            solution(x+N//2, y+N//2, N//2)
            return
      if num == 0:
        result.append(0)
      else: # color == 1
        result.append(1)
    
    
    solution(0,0,N)
    print(result.count(0))  # result의 0의 개수 -> 하얀 종이 개수
    print(result.count(1))  # result의 1의 개수 -> 파란 종이 개수
    

    'sparta > 알고리즘' 카테고리의 다른 글

    [항해99]알고리즘_08  (0) 2021.06.22
    [항해99]알고리즘_06  (0) 2021.06.21
    [항해99]알고리즘_05  (0) 2021.06.20
    [항해99]알고리즘_04  (0) 2021.06.18
    [항해99]알고리즘_03  (0) 2021.06.17

    댓글

Designed by Tistory.