2630

날짜 : 2022. 12. 21

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
graph = []
w, b = 0, 0

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


def check(r, c, l):
    #print(r, c, l)
    default = graph[r][c]  # 기준 색깔
    flag = True
    for i in range(r, r + l):
        for j in range(c, c+l):
            if graph[i][j] in range(2) and graph[i][j] != default: # 서로 다른것 발견
                flag = False
                break
        if not flag:
            break
    if not flag:
        check(r, c, l // 2)
        check(r + (l // 2), c, l // 2)
        check(r, c + (l // 2), l // 2)
        check(r + (l // 2), c + (l // 2), l // 2)
        return

    for i in range(r, r + l):
        for j in range(c, c + l):
            graph[i][j] = -1  # 확인
    if flag:  # 색깔이 모두 일정
        if default == 1:  # blue
            global b
            b += 1
        else:
            global w
            w += 1
    return


check(0, 0, n)
print(w, b)
"""for i in graph:
    print(i)"""

 

 

풀이

- 디폴트를 먼저 설정한 후에 디폴트 값과 서로 다른 경우(0 또는 1) 기준인 변의 길이를 1/2배 하는 방식으로 줄여나가면서 재귀 방식으로 풀이했다.

 

 

알게된 점

- 처음 for문으로 문제를 해결하려다 너무 난잡해지는것같아 flag를 통해 곧바로 이중 for문을 탈출하고 변의 길이를 나누어 파트마다 재귀하는 방식으로 바꾸었는데 오히려 가독성도 좋아졌고 한번에 문제가 해결됐다.

 

 

참고 사이트

-