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

문제

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

풀이

처음에 흰색으로만 되어 있는 조건을 n*n으로 안하고 n으로 해줬었는데, 어떻게 잘 발견해서 n*n으로 잘 고쳐줬다!!!
처음부터 끝까지 스스로 푼 문제!! 기특 😂😂

import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

wcnt = 0 # 흰색 개수
bcnt = 0 # 파란색 개수

def sol(n, x, y): # n: 현재 변의 길이, x: 현재 좌표의 행 위치, y: 현재 좌표의 열 위치
    global wcnt, bcnt
    
    wtmp = 0
    btmp = 0
    for i in range(n):
        for j in range(n):
            if arr[x+i][y+j] == 1:
                btmp += 1
            else:
                wtmp += 1
    if wtmp == n*n: # 흰색으로만
        wcnt += 1
        return
    elif btmp == n*n: # 파란색으로만
        bcnt += 1
        return
    else : # 같은 색으로만 이루어져 있는 게 아닐 때
        sol(n//2, x, y)
        sol(n//2, x, y + n//2)
        sol(n//2, x + n//2, y)
        sol(n//2, x + n//2, y + n//2)   
        

sol(n, 0, 0)

print(wcnt)
print(bcnt)

22.05.13 다시 풀어보기

다시 풀어볼 땐 기존의 방식대로 풀고 또 다른 방법으로 풀 수 있는 방식이 있는지 찾아보았다. 첫번째 블럭의 색깔을 기준으로 현재 변의 길이만큼 for문을 돌며 색깔이 다른 것이 있을 때마다 재귀를 돌아서 나눠주고 색깔이 같은지 확인하는 풀이였다.

혼자 코드를 쓰고 발견한 놓친 부분은 다음과 같다.
바로 재귀를 돌리며 제 4사분면까지 판단이 끝났을 땐 무조건 같은 색깔이 있는 것끼리 나뉘어졌으므로 더 이상 재귀가 또 돌면 안되는데, return을 써주지 않아서 계속 재귀가 돌게 했다. 즉 만약 현재 길이에서 가지는 색깔이 달라 4사분면까지 재귀를 돌고 끝나야 하는데 return이 없으면 한 번 판단할 때마다 끝까지 파고 들어서 한 변의 길이가 1이 될 때까지 재귀를 계속 돌게 된다. 따라서 답으로 매우 큰 값이 나온다.

정리하면, 한 변의 길이가 k//2인 depth에서 재귀가 한 번 돌고 끝나야 하는데,
k == 1일 때까지 계속 재귀를 돌게 된다.
그래서 재귀를 한 번 돌리고 판단이 반드시 끝날 수밖에 없는 곳에 꼭 return을 써줘야 한다.

한편, 그 다음 한 변의 길이가 2인 상태일 떄 해당 depth에서 color가 모두 같다면, for문 안의 if문에 들어가지 않고 if color == 0인 곳으로 가서 white에 1을 더해주게 된다.

# 2630번 색종이 만들기
# 27:00

import sys
input = sys.stdin.readline

n = int(input())
paper = [list(map(int, input().split())) for _ in range(n)]
white = 0 # 하얀색의 개수
blue = 0 # 파란색의 개수

def sol(k, x, y): # k 한 변의 길이 x 현재 x축 좌표 y 현재 y축 좌표
    global white, blue
    color = paper[x][y] # 첫번째 블럭의 색깔

    for i in range(k):
        for j in range(k):
            if color != paper[x + i][y + j]:
                # 제 1사분면
                sol(k//2, x, y)
                # 제 2사분면
                sol(k//2, x, y+k//2)
                # 제 3사분면
                sol(k//2, x+k//2, y)
                # 제 4사분면
                sol(k//2, x+k//2, y+k//2)
                # return의 존재 이유
                # 제 4사분면까지 한번씩만 재귀를 돌면 항상 판단이 끝남
                # but, return이 없으면 한 번 판단할 때마다 끝까지 파고 들어서
                # 한 변의 길이가 1이 될 때까지 계속 재귀를 돌 것
                return
    
    # 4 사분면까지 다 돈 이후 동일한 색깔만 있을 때
    if color == 0:
        white += 1
        return
    else:
        blue += 1
        return


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