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

문제

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

풀이

최초 풀이

• 0, 0 좌표의 값을 저장한다.
• x, y 좌표까지 모두 훑으면서 0, 0 좌표와 색을 비교한다.
• 다른 값 발견시 4분면으로 분화시켜서 재귀를 돌린다.

def slice(fromx, tox, fromy, toy):
    global paper, white, blue
    color = paper[fromx][fromy]

    check = 1
    for x in range(fromx, tox):
        if check == 0: break
        for y in range(fromy, toy):
            if paper[x][y] != color:
                slice(fromx, tox // 2, fromy, toy // 2) # 1
                slice(tox // 2, tox, fromy, toy // 2) # 4
                slice(fromx, tox // 2, toy // 2, toy) # 2
                slice(tox // 2, tox, toy // 2, toy) # 3
                check = 0
                break

    if check and color == 0: white += 1
    if check and color == 1: blue += 1

n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

white, blue = 0, 0
slice(0, n, 0, n)
print(white, blue)

접근 방식은 올바랐으나, tox, toy 나누기로 인해
인자를 잘못 받아 재귀를 무한하게 돌고있었다.

이 때문에 tox, toy를 직접 나누어 구하는 방식 말고
n 값을 나눠서 더하는 걸로 바꾸어 보았다.

2차 풀이

def slice(x, y, n):
    global paper, white, blue
    color = paper[x][y]

    check = 1
    for i in range(x, x+n):
        if check == 0: break
        for j in range(y, y+n):
            if paper[i][j] != color:
                slice(x, y, n//2) # 1
                slice(x+n//2, y, n//2) # 4
                slice(x, y+n//2, n//2) # 2
                slice(x+n//2, y+n//2, n//2) # 3
                check = 0
                break

    if check and color == 0: white += 1
    if check and color == 1: blue += 1

n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

white, blue = 0, 0
slice(0, 0, n)
print(white)
print(blue)

잘 된다!