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

문제

https://www.acmicpc.net/problem/2630

백준 단계별 풀이 - 분할 정복

---

풀이

전체 코드

# 분할 정복

# 메모리: 31120KB / 시간: 52ms

# 1
from sys import stdin


input = stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]

ret = [0, 0]

# 2
def quadtree(row: int, col: int, size: int) -> None:
    color: int = paper[row][col]

    for i in range(row, row+size):
        for j in range(col, col+size):
            if paper[i][j] != color:
                half = size // 2
                # 좌상, 좌하, 우상, 우하 순서대로 재귀
                quadtree(row, col, half)
                quadtree(row+half, col, half)
                quadtree(row, col+half, half)
                quadtree(row+half, col+half, half)
                return
    ret[color] += 1  # 모든 색이 같다면 해당 색깔 결과값(0또는 1)에 1 추가

# 3
quadtree(0, 0, N)
print(f"{ret[0]}\n{ret[1]}")

---

단계별 풀이

1. 입력값 할당

from sys import stdin


input = stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]

ret = [0, 0]

• N: 입력줄의 갯수(=행 갯수)
• paper: 입력 배열값을 저장할 2차원 리스트.
  • 행만큼 순회하며 각 줄의 입력값을 정수형으로 변환 후 리스트로 만들어준다.
  • [[0번째 행의 원소들], [1번째 행의 원소들]...]
• ret = [0, 0]: 결과값을 저장할 리스트. 0번째 인덱스는 흰색, 1번째 인덱스는 파란색값을 저장.

 

2. 쿼드트리 함수 작성

def quadtree(row: int, col: int, size: int) -> None:
    color: int = paper[row][col]

    for i in range(row, row+size):
        for j in range(col, col+size):
            if paper[i][j] != color:
                half = size // 2
                # 좌상, 좌하, 우상, 우하 순서대로 재귀
                quadtree(row, col, half)
                quadtree(row+half, col, half)
                quadtree(row, col+half, half)
                quadtree(row+half, col+half, half)
                return
    ret[color] += 1  # 모든 색이 같다면 해당 색깔 결과값(0또는 1)에 1 추가

• 재귀형태로 작성
• row: 행, col: 열, size: 색종이의 크기
• color: 비교하며 검사할 기본값. 검사할 부분의 제일 첫번째 값으로 할당.
• 주어진 행/열값부터 행+크기/열+크기 값까지 순회하며 체크한다.
  • 만약, 현재 값 색종이[i][j]이 기본값 color과 다르다면,
  • half: 주어진 사이즈를 반으로 나눈값, 즉 4등분한 색종이의 한 변의 길이
  • 왼쪽 위/아래, 오른쪽 위/아래 순서로 재귀호출을 실시한다.
  • 호출을 마치면 return으로 함수를 종료
• 모든 값이 같다면 ret[color]값에 1을 더해준다.
  • 흰색은 0, 파란색은 1로 주어지므로 color값이 1이라면 ret[0, 1], 0이라면 ret[1, 0]이 된다.

 

3. 함수 호출 및 결과값 출력

quadtree(0, 0, N)
print(f"{ret[0]}\n{ret[1]}")

• 0, 0, N을 인자값으로 넣어 함수를 호출한다.
• 흰색, 파란색 순서대로 한줄씩 출력하라고 했으므로 ret[0], ret[1]을 차례대로 출력.