[Python] 프로그래머스 / Summer/Winter Coding(2019) / 지형 이동

문제 링크

 

생각보다 섬세함이 필요한 BFS

BFS 그거 그냥 queue 만들어서 while queue 하면 끝 아님? 싶을 수 있겠지만... BFS에 익숙해진 나머지, 근의 공식 사용하듯이 그렇게 아무 생각 없이 풀면 안 된다는 것을 깨달았다. 일단 이 문제는, MST(최소 스패닝 트리) 방식으로도 충분히 잘 풀 수 있다. 그것도 물론 좋은 방법이지만, 나는 BFS 풀이로 풀었다.

 

오답 풀이

import heapq

def solution(land, height):
    N = len(land)
    
    queue = [(0, 0, 0)] 
    seen = [[False] * N for _ in range(N)] 
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        ladder, cx, cy = heapq.heappop(queue)
        
        if seen[cx][cy]:
            continue 
        
        seen[cx][cy] = True
        current_height = land[cx][cy]
        
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N:
                if not seen[nx][ny]:
                    height_diff = abs(land[nx][ny] - current_height)
                    if height_diff <= height:
                        heapq.heappush(queue, (ladder, nx, ny))
                    else:
                        heapq.heappush(queue, (ladder+height_diff, nx, ny)) 
    
    return ladder

 

정답 풀이

이 정답코드는 오답 풀이에서 달라진 점은 딱 하나 밖에 없다.

queue에 answer를 집어넣어서 관리하느냐, 아니면 while문 밖에서 answer를 미리 선언해놓고 while문 내에서 업데이트만 하느냐.

 

사실 queue에 answer를 집어넣는 방식으로도, 풀리는 경우가 있을 수는 있다.

그러나 이 문제의 경우 while queue 안에 break 조건문이 없다. 즉, 최적해를 찾은 이후로도 queue가 고갈될 때까지 탐색은 계속된다는 것. 그게 싫으면 seen 행렬을 매번 검토해서 다 True되면 break하는 방법이 있긴 한데, 그러면 아마 시간복잡도를 못 견딜 것이다.

 

아무튼, 그렇다보니 queue에 answer를 넣어서 관리했는데 별도의 break 조건이 없는 이상, 반환되는 답변은 최적해가 아니라 마지막으로 탐색된 해일 것이다. 그러므로 위의 오답 코드가 잘못된 방법인 것.

import heapq

def solution(land, height):
    N = len(land)
    
    queue = [(0, 0, 0)] 
    seen = [[False] * N for _ in range(N)] 
    answer = 0 
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    while queue:
        ladder, cx, cy = heapq.heappop(queue)
        
        if seen[cx][cy]:
            continue 
        
        seen[cx][cy] = True
        answer += ladder 
        
        current_height = land[cx][cy]
        
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N:
                if not seen[nx][ny]:
                    height_diff = abs(land[nx][ny] - current_height)
                    if height_diff <= height:
                        heapq.heappush(queue, (0, nx, ny))
                    else:
                        heapq.heappush(queue, (height_diff, nx, ny)) 
    
    return answer

 

시간복잡도

실전 코테를 풀 때는 시간복잡도를 생각을 안 할 수가 없다. 여기에서는 문제조건상 N <= 2000 이므로, O(N^3)은 절대 안 되고, 최대 O(N^2 logN)이어야 한다. 대충 계산했을 때 10^8 (1억) 이 넘어간다 싶으면 "어?" 해야 할 줄 알아야 한다.

 

근데 코드에서 시간복잡도 계산이 생각보다 어려운 과정이라서, 이 정답 코드를 예시로 쉽게 시간복잡도를 구하는 방법을 작성하고자 한다.

 

일단은, 

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

 

이런 짜잘짜잘한 코드는 무시해도 좋다. Big-O 규칙 상 뭘 더하고 빼고 하는 건 사실상 무시해도 되는 과정이다.

 

위에서 신경써야 할 부분은 딱,

    seen = [[False] * N for _ in range(N)] 
    
    while queue:
        ladder, cx, cy = heapq.heappop(queue)
        
                    if height_diff <= height:
                        heapq.heappush(queue, (0, nx, ny))
                    else:
                        heapq.heappush(queue, (height_diff, nx, ny))

 

이 부분들이 전부이다. N^2의 크기의 맵에 대해, 하나 하나마다 heappop 한 번, heappush를 또 몇 번 정도 해야 하니 각 칸마다 logN의 시간복잡도가 든다. 그러므로 이 코드의 시간복잡도는 O(N^2 logN)이다.

 

_

loewen.tistory.com