쿼드압축 후 개수 세기

날짜 : 2023. 10. 04

사용 언어 : python

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68936?language=python3

 

코드

def solution(graph):
    dist = len(graph)
    def check(r, c, length):
        # print(r, c, length)
        if length == 0: return
        flag = graph[r][c]  # 기준값 저장
        for i in range(r, r + length):
            for j in range(c, c + length):
                if flag != graph[i][j]:  # 압축 불가능 -> 재귀
                    check(r, c, length // 2)
                    check(r, c + length // 2, length // 2)
                    check(r + length // 2, c, length // 2)
                    check(r + length // 2, c + length // 2, length // 2)
                    break
            else:
                continue
            break
        else:  # 최종 압축 가능
            for i in range(r, r + length):
                for j in range(c, c + length):
                    graph[i][j] = -1  # 압축처리(기준점 제외 가산 x)
            graph[r][c] = flag
        return
    res = [0, 0]
    check(0, 0, dist)
    for i in range(dist):
        for j in range(dist):
            if graph[i][j] == 0: res[0] += 1
            elif graph[i][j] == 1: res[1] += 1
    # for i in graph:
    #     print(i)
    return res

 

 

풀이

- 기준점 (r, c)에서 시작해 기준이 되는 변의 길이만큼 돌면서 graph[r][c]의 값과 다른 경우 재귀하고, 만약 이중 for문을 통과한 경우 기준점을 기준으로 해당 (변의 길이)^2 만큼의 면적을 압축한다.

- 변의 길이는 점점 절반으로 줄어들기 때문에 2로 나누면서 구현했고, 각각의 점은 4개이기 때문에 위 그림과 같이 check()함수를 4번 호출해서 재귀했다.

- 만약 압축하는 경우에는 기준점 하나는 무조건 남겨야 개수를 셀 때 남겨놓을 수 있기 때문에 해당 면적을 전부 -1처리한 다음 기준점만 기존의 값으로 설정해 놓는다.

- 맨 처음에는 (0, 0)에서 시작하고, 변의 길이만큼 탐색하기 때문에 처음 길이 dist는 len(graph)와 같다.

- 해당 함수를 전부 탈출한 다음 graph의 값을 이중 for문을 통해서 탐색하면서 가산한 다음 값을 리턴한다.

 

 

알게된 점

- 문제 자체는 조금 까다로웠지만 이전에 백준에서 풀었던 문제랑 유사했기 때문에 곧바로 아이디어를 도출하고 풀 수 있었다.

- 다만 마지막 부분 디버깅 하면서 계속 원하는 값이 나오지 않아 재귀 depth를 체크해 보니 확실하게 들어가지 않은 것을 찾았고, 맨 처음 dist 설정을 잘못했다는 점을 확인했다.

- dist 설정은 graph 자체의 한 변의 길이로 설정해야 한다는 점을 간과했었다.

 

 

 

참고 사이트

-