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

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

2630번: 색종이 만들기

 

문제 한줄 이해

-주어진 종이가 모두 같은 색으로 칠해져 있지 않다면 가로 세로로 중간 부분을 잘라 n/2 *n/2 종이를 만들어가면서 모두 같은 색으로 이루어지게 만들기

 

생각난 풀이

1번째 방법: 같은 격자내에 같은 숫자들만 있어야 한다는 것에 초점을 두고 접근했다.

import sys

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

#방문 체크
visited = [[False for i in range(n)] for i in range(n)]

def dfs(x,y,cnt):
#  범위가 벗어나면 종료
    if x+cnt > n or y+cnt>n:
        return
# 현재 색깔과 다르다면 종료
    for i in range(x,x+cnt):
        for j in range(y,y+cnt):
            if nowcolor != graph[i][j]:
                return
# 종료가 되지 않았다면 확인한 범위 내에서는 문제가 없으니
# 체크 표시하고 탐색범위 증가
    for i in range(x,x+cnt):
        for j in range(y,y+cnt):
            visited[i][j] = True
    dfs(x,y,cnt+1)
white = 0
blue = 0
for i in range(n):
    for j in range(n):
        nowcolor = graph[i][j]
        if visited[i][j] == False:
            dfs(i,j,1)
            if nowcolor == 1:
                blue += 1
            else:
                white +=1
print(white)
print(blue)

하지만 n/2로 범위가 줄어 든다는 점을 놓쳤고 이 같은 경우에

1 0 0 0

1 0 0 0

1 1 1 1

1 1 1 1 일때 문제에서 제시한 규칙에 어긋나게 된다는 것을 알았다.

 

2번째 방법: 문제의 규칙에 충실

import sys

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

def dfs(x,y,n):
    global white
    global blue
    nowcolor = graph[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
#다르다면 그 즉시 잘라 나간다.
            if graph[i][j] != nowcolor:
                dfs(x,y,n//2)
                dfs(x+n//2,y,n//2)
                dfs(x+n//2,y+n//2,n//2)
                dfs(x,y+n//2,n//2)
                return
#함수가 종료 되지 않았다면
    if nowcolor == 1:
        blue += 1
    else:
        white += 1
white = 0
blue = 0
dfs(0,0,n)
print(white)
print(blue)