[프로그래머스 LV 2] 쿼드압축 후 개수 세기 (파이썬/python)

https://programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

코드가 세개 있다. 

첫번째는 틀린코드, 쓰다 만 코드이다

 

첫번째 풀이법으로 생각한게 매 경우 bfs로 같은 숫자만으로 구성되어있는지 확인한 후

같으면 합치고 틀리면 나누고 이러는건데

배열 전체를 전달하며 함수를 쓰려니 이차원배열을 십자모양으로 나누는 법을 도저히 구현하지 못 하겠다.

 

>>>그래서 인덱스로 접근한 

>>>두번째 풀이법으로 문제를 풀었다

 

세번째 풀이법은 첫번째 풀이법을 고친 맞는 코드다

하지만 시간복잡도가 애바마라서 몇개는 맞고(맞아도 시간복잡도가 너무 큼) 몇개는 시간초과가 난다

 

 

첫번쨰 틀린풀이(컴파인 안됨)

def bfs(arr):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    # 방문기록
    visit = [[0] * len(arr) for i in range(len(arr))]
    q = []
 
    # 방문 확인과 함께 같은 값인지 저장하는 역할 겸용
    visit[0][0] = arr[0][0]
    q.append([0, 0])
 
    while q:
        location = q.pop(0)
        x = location[0]
        y = location[1]
 
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx >= len(arr) or ny < 0 or ny >= len(arr) or visit[nx][ny] != 0:
                continue
            # 혹시 값이 다르면 bfs 빠져나오고 값이 다름을 알려줌
            # 배열이 0과 1로 구성되어있기때문에 -1로 알려줌!
            if visit[x][y] != visit[nx][ny]:
                return -1
            # 위 조건이 아닐경우 bfs탐색 실시함
            visit[nx][ny] = arr[nx][ny]
            q.append([nx][ny])
 
    #값이 같을 경우 어떤 값으로 같은지 알려줌
    return arr[0][0]
 
def devide(arr):
    # 전체를 조사, 같은 숫자가 있는지 확인
    num = bfs(arr)
 
    # 1이나 0일경우 상자를 하나로 합쳐줌!
    if num ==1 or num ==0:
        for i in range(len(arr)):
            for j in range(len(arr)):
                arr[i][j] = num
 
    # -1일경우 다시 devide 시작
    else :
        for i in range(len(arr)):
    # 이차원배열이라 자르는게 너무 힘들어!! 
            
 
 
 
 
 
def solution(arr):
    copy_arr = [[]]
    answer = []
    n = 1
    # 2의 몇 승인지 구했음
    while 1:
        if 2 ** n == len(arr):
            break
        n += 1
 
    x, y = len(arr), len(arr)
    # 최대 n번 갈라짐
    copy_arr = devide(arr)
    return answer

 

두번쨰로 풀어 맞은 풀이

def solution(arr):
    answer = [0, 0]
    n = len(arr)
 
    def devide_cheak(x, y, n):
        first = arr[x][y]
 
        # 전부 같은 숫자인지 탐색
        for i in range(x, x + n):
            for j in range(y, y + n):
                # 만약 다르다면 재귀적으로 분할해 나간다.
                if arr[i][j] != first:
                    half_n = n // 2
                    devide_cheak(x, y, half_n)
                    devide_cheak(x, y + half_n, half_n)
                    devide_cheak(x + half_n, y, half_n)
                    devide_cheak(x + half_n, y + half_n, half_n)
                    return
 
        # 만약 전부 같다면 같은 숫자의 value를 1 올려준다.
        answer[first] += 1
        return
 
    devide_cheak(0, 0, n)
    return answer

def solution(arr):
    n = len(arr)
    answer = [0, 0]
 
    def bfs(x, y, n):
        # 오른쪽, 밑만 확인하면 됨
        dx = [0, 1]
        dy = [1, 0]
        # 방문기록
        visit = [[0] * len(arr) for i in range(len(arr))]
        q = []
        visit[x][y] = 1
 
        q.append([x, y])
 
        while q:
            location = q.pop(0)
 
            x1 = location[0]
            y1 = location[1]
 
            for i in range(2):
                nx, ny = x1 + dx[i], y1 + dy[i]
                if nx < x or nx >= x + n or ny < y or ny >= y + n or visit[nx][ny] != 0:
                    continue
                # 혹시 값이 다르면 bfs 빠져나오고 값이 다름을 알려줌
                # 배열이 0과 1로 구성되어있기때문에 -1로 알려줌!
                if arr[x][y] != arr[nx][ny]:
                    return -1
                # 위 조건이 아닐경우 bfs탐색 실시함
                visit[nx][ny] = 1
                q.append([nx, ny])
 
        # 값이 같을 경우 어떤 값으로 같은지 알려줌
        print(arr[x][y])
        return arr[x][y]
 
    def devide(x, y, n):
        # 전체를 조사, 같은 숫자가 있는지 확인
        num = bfs(x, y, n)
 
        # 1이나 0일경우 상자를 하나로 합쳐줌!
        if num == 1 or num == 0:
            answer[num] += 1
            return
 
        # -1일경우 다시 devide 시작
        else:
            # if n == 1:
            #     return
            half_n = n // 2
 
            devide(x, y, half_n)
            devide(x + half_n, y, half_n)
            devide(x, y + half_n, half_n)
            devide(x + half_n, y + half_n, half_n)
            return
 
    devide(0, 0, n)
 
    return answer
 
 
 

 

세번째풀이 시간초과 ㅋㅋㅋㅋㅋ