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

신효민·2024년 10월 17일

분할정복 실버 알고리즘 재귀 코딩테스트

알린이 탈출기[ 알고리즘 ]

목록 보기

1/3

📖 문제

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

😭알린이의 실수😭

나눠진 구역들의 시작점과 끝점의 좌표를 함수의 파라미터로 설정하여
나눠진 구역에 대해서 1 또는 0으로만 되어있는지 검사를 하려고 했다.
Ex) divide_paper(n,a,b,c,d)
-> 파라미터가 너무 많아져서 함수 자체가 복잡해보임
-> 로직을 짜는데 복잡해짐
-> 결국 , 끝점의 좌표값을 처리하기 어려웠고 값도 정확하게 나오지 않음.

😎 풀이 ( 해결책 )

끝점을 없애고 시작점만을 기준으로 로직을 세웠다.

Ex ) divide_paper(n,a,b,c,d) -> divide_paper(n,a,b)
여기서 n은 나눠진 구역의 변의 길이 , (a,b)는 시작점의 좌표

자세한 풀이는 주석 참고!

N=int(input())

def divide_paper(n,a,b): 
    global blue_paper
    global white_paper
    if n==1:
        if arr[a][b]==1: # 1일때 파란색 색종이 갯수 +1
            blue_paper+=1
        else:
            white_paper+=1 # 0일때 하얀색 색종이 갯수 +1
        return

    # 나눠진 구역이 1 또는 0 으로만 이루어져있는지 검사하는 부분
 	"""
    여기서 (a,b) , ( a+(n-1) , b+(n-1) ) 좌표가
    나눠진 구역의 시작점과 끝점이다.
    """
    flag=False
    t=arr[a][b]
    for i in range(a,a+n):
        if flag==True:
            break
        for j in range(b,b+n):
            if arr[i][j]!=t:
                flag=True
	
    # 나눠진 구역이 1또는 0으로만 이루어져있을때
    if flag==False:
        if t==1:
            blue_paper+=1
            return
        elif t==0:
            white_paper+=1
            return
            
	# 나눠진 구역이 1 과 0이 섞여있을때
    k=n//2
    # 4개의 구역으로 나누고 함수 호출
    divide_paper(k,a,b) 
    divide_paper(k,a,b+k) 
    divide_paper(k,a+k,b)
    divide_paper(k,a+k,b+k)

arr=[[0]*N for _ in range(N)]

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

blue_paper=0 # 파란색 색종이 갯수
white_paper=0 # 하얀색 색종이 갯수
divide_paper(N,0,0) # 색종이 만들기 함수
print(white_paper) 
print(blue_paper)

👨‍🎓 더 성장..

다른 사람의 풀이를 한번 봐보자.

이 분의 풀이를 보고 내 코드에서 피드백할 부분을 찾아보자.
( 위 사진이 [출처] )

import sys

N = int(sys.stdin.readline())
color_matrix = [ [] for _ in range(N)]
for i in range(N):
    color_matrix[i] = list(map(int,sys.stdin.readline().strip().split()))

white=0
black=0

def dfs(n,x,y): # 다음 쪼갠부분에도 시작포지션 그래서 x,y 매개변수
    global black
    global white
    half = n//2
    if n==1:
        if color_matrix[x][y] ==0:
            white += 1
        else:
            black += 1
        return
    
    # 구역이 1 또는 0으로만 되어 있는지 검사하는 부분
    for i in range(x,x+n):
        for j in range(y,y+n):
            if color_matrix[i][j] != color_matrix[x][y]:
                dfs(half, x, y) # 1사분면
                dfs(half, x+half, y) # 2사분면
                dfs(half, x, y+half) # 3사분면
                dfs(half, x+half, y+half) # 4사분면
                return 
    
  	# 구역이 1 또는 0으로만 되어 있다면
    if color_matrix[x][y] ==0:
        white += 1
    else:
        black += 1

dfs(N,0,0)

print(white)
print(black)