[알고리즘] 백준 2630번 색종이 만들기 + 리팩토링

 

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

 

 

 

알고리즘 분류

분할 정복
재귀

(하연이 코드)

import sys

def count_colors(x, y, size):
    global white, blue
    initial_color = paper[x][y]  # 현재 영역의 첫 번째 색상
    same_color = True  # 현재 영역이 모두 같은 색인지 확인하는 플래그

    # 현재 영역의 모든 칸을 검사하여 같은 색인지 확인
    for i in range(x, x + size):
        for j in range(y, y + size):
            if paper[i][j] != initial_color:  # 다른 색이 발견되면
                same_color = False  # 같은 색이 아님을 표시
                break  # 내부 루프 중지
        if not same_color:  # 같은 색이 아님이 확인되면
            break  # 외부 루프 중지

    if same_color:  # 영역이 모두 같은 색인 경우
        if initial_color == 0:  # 흰색일 경우
            white += 1  # 흰색 카운트 증가
        else:  # 파란색일 경우
            blue += 1  # 파란색 카운트 증가
    else:  # 영역이 다른 색이 섞여 있는 경우
        half_size = size // 2  # 영역을 네 부분으로 나눌 크기 계산
        count_colors(x, y, half_size)  # 1사분면
        count_colors(x, y + half_size, half_size)  # 2사분면
        count_colors(x + half_size, y, half_size)  # 3사분면
        count_colors(x + half_size, y + half_size, half_size)  # 4사분면

if __name__ == '__main__':
    n = int(sys.stdin.readline())  # 색종이의 크기 입력 받기
    paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]  # 색종이의 색상 입력 받기

    white, blue = 0, 0  # 흰색과 파란색 카운트 초기화
    count_colors(0, 0, n)  # 전체 색종이에 대해 함수 호출
    print(white)  # 흰색 색종이 조각 개수 출력
    print(blue)  # 파란색 색종이 조각 개수 출력

풀이
우선 함수를 생성하는데 색종이 안에 같은 색인지 확인하는 재귀 함수를 생성한다. 

재귀함수의 요소

1. 종료조건
2. 호출 스택

여기서 종료 조건은

if same_color:  # 영역이 모두 같은 색인 경우
        if initial_color == 0:  # 흰색일 경우
            white += 1  # 흰색 카운트 증가
        else:  # 파란색일 경우
            blue += 1  # 파란색 카운트 증가

 

이 부분이다. 그리고 아래에서 함수가 계속 호출됨

else:  # 영역이 다른 색이 섞여 있는 경우
        half_size = size // 2  # 영역을 네 부분으로 나눌 크기 계산
        count_colors(x, y, half_size)  # 1사분면
        count_colors(x, y + half_size, half_size)  # 2사분면
        count_colors(x + half_size, y, half_size)  # 3사분면
        count_colors(x + half_size, y + half_size, half_size)  # 4사분면

 

+ 그리고 여기 영역을 나누어서 확인하고 있는데 개인적으로 이 부분에서 이중리스트 인덱스 확인하는 데서 애먹었다. 후 ~ 

 

 

 

 

 

확인해보니 현재 영역 안의 모든 칸을 검사하여 같은 색으로 확인하는 부분은 굳이 재귀함수 안에 있을 필요가 없다고 생각해서 함수를 따로 분리해보기로 했다 . 즉. 리팩토링을 해보겠다는 뜻. 

def is_same_colour(x, y, size):
    same_color = True
    initial_color = paper[x][y]
    # 현재 영역의 모든 칸을 검사하여 같은 색인지 확인
    for i in range(x, x + size):
        for j in range(y, y + size):
            if paper[i][j] != initial_color:  # 다른 색이 발견되면
                same_color = False  # 같은 색이 아님을 표시
                break  # 내부 루프 중지
        if not same_color:  # 같은 색이 아님이 확인되면
            break  # 외부 루프 중지
    return same_color

# 색종이 만들기
import sys

def is_same_colour(x, y, size):
    same_color = True
    initial_color = paper[x][y]
    # 현재 영역의 모든 칸을 검사하여 같은 색인지 확인
    for i in range(x, x + size):
        for j in range(y, y + size):
            if paper[i][j] != initial_color:  # 다른 색이 발견되면
                same_color = False  # 같은 색이 아님을 표시
                break  # 내부 루프 중지
        if not same_color:  # 같은 색이 아님이 확인되면
            break  # 외부 루프 중지
    return same_color

def count_colors(x, y, size):
    global white, blue
    initial_color = paper[x][y]  # 현재 영역의 첫 번째 색상
    same_color = is_same_colour(x, y, size)  # 현재 영역이 모두 같은 색인지 확인하는 플래그

    if same_color:  # 영역이 모두 같은 색인 경우
        if initial_color == 0:  # 흰색일 경우
            white += 1  # 흰색 카운트 증가
        else:  # 파란색일 경우
            blue += 1  # 파란색 카운트 증가
    else:  # 영역이 다른 색이 섞여 있는 경우
        half_size = size // 2  # 영역을 네 부분으로 나눌 크기 계산
        count_colors(x, y, half_size)  # 1사분면
        count_colors(x, y + half_size, half_size)  # 2사분면
        count_colors(x + half_size, y, half_size)  # 3사분면
        count_colors(x + half_size, y + half_size, half_size)  # 4사분면

if __name__ == '__main__':
    n = int(sys.stdin.readline())  # 색종이의 크기 입력 받기
    paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]  # 색종이의 색상 입력 받기

    white, blue = 0, 0  # 흰색과 파란색 카운트 초기화
    count_colors(0, 0, n)  # 전체 색종이에 대해 함수 호출
    print(white)  # 흰색 색종이 조각 개수 출력
    print(blue)  # 파란색 색종이 조각 개수 출력

이렇게 해서 원래 코드를 수정했다. 다행히 잘 돌아가는 것 까지 확인했다. 끝.