[알고리즘] 백준 2630 색종이 만들기 (파이썬 풀이)

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

2630번: 색종이 만들기

해결코드

n = int(input())
square = [[0]*n for i in range(n)]

for i in range(n):
    square[i] = list(map(int, input().split()))

white = 0
blue = 0

def color(x,y,n):
    global white, blue
    cnt = square[x][y]
    for i in range(x,x+n):
        for j in range(y, y+n):
            if cnt != square[i][j]:
                color(x,y,n//2)
                color(x,y+n//2,n//2)
                color(x+n//2,y,n//2)
                color(x+n//2,y+n//2,n//2)
                return
    if cnt==0:
        white += 1
        return
    else:
        blue += 1
        return
color(0,0,n)
print(white)
print(blue)

문제풀이

분할 정복 문제로 정해진 한 면이 같은 수로 채워지지 않으면 같은 수로 채워지는 면이

나올 때까지 계속해서 4등분하는 방식이다.

 

코드를 보자

 

n = int(input())
square = [[0]*n for i in range(n)]

n에 한 변의 길이를 입력받고 sqaure에는 n*n의 0으로 채워진 정사각형 리스트를 담아준다.

 

for i in range(n):
    square[i] = list(map(int, input().split()))

square의 각 칸에 들어갈 숫자를 입력받는다.

 

white = 0
blue = 0

마지막에 출력할 흰 색, 파란색 변수를 선언하고 0으로 초기화 한다.

 

color함수를 살펴보자

 

def color(x,y,n):
    global white, blue
    cnt = square[x][y]

전역변수로 white,blue를 불러오고 cnt에는 square[x][y]의 값을 저장해준다(첫 x,y는 무조건 0,0)
    for i in range(x,x+n):
        for j in range(y, y+n):
            if cnt != square[i][j]:
                color(x,y,n//2)
                color(x,y+n//2,n//2)
                color(x+n//2,y,n//2)
                color(x+n//2,y+n//2,n//2)
                return

square의 모든 칸을 검사해본다 -> 하나라도 cnt값과 일치하지 않으면(색이 다르면)

square를 4등분한 함수를 계속해서 실행한다(재귀) return으로 다음코드실행 방지
    if cnt==0:
        white += 1
        return

만약 cnt값이 0이라면(흰색) white에 1씩 더해준다.
    else:
        blue += 1
        return

파란색이라면 blue에 1씩 더해준다.

 

color(0,0,n)
print(white)
print(blue)

함수를 처음 실행할 떄는 x,y 좌표값은 0,0으로 넘겨준다.

함수를 실행한 뒤 도출되는 white,blue를 각각 출력해준다.