[프로그래머스] DFS/BFS : level2. 게임 맵 최단거리

A. 문제설명

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

2차원 배열로 맵이 주어지고, 시작지점에서 종료지점까지 최단거리를 구하는 문제.

B. 초기 답안

def solution(maps):
    global dir_x, dir_y
    dir_x = [0, 1, 0, -1]
    dir_y = [1, 0, -1, 0]
    visited = [[999999]*len(maps[0]) for _ in range(len(maps))]
    cnt = sum(j == 1 for i in maps for j in i)
    
    visited[0][0] = 1
    dfs(maps, visited, 0, 0, 1)

    return -1 if visited[len(maps)-1][len(maps[0])-1] == 999999 else visited[len(maps)-1][len(maps[0])-1]
    
def dfs(maps, visited, x, y, depth):
    for i in range(4):
        next_x = x + dir_x[i]
        next_y = y + dir_y[i]
        
        if 0 <= next_x < len(maps) and 0 <= next_y < len(maps[0]):
            if maps[next_x][next_y] == 1 and visited[next_x][next_y] > depth+1:
                visited[next_x][next_y] = depth+1
                dfs(maps, visited, next_x, next_y, depth+1)

C. 개선

dfs로 풀 시, 효율성 초과 에러 발생.

출처: https://velog.io/@vagabondms/DFS-vs-BFS

원인은 위의 사진에서 확인할 수 있다.

 

1. 원리: DFS는 2번 노드를 탐색하는데 4초의 시간이 걸리고, BFS는 2초의 시간이 걸린다.

2. 최단거리 탐색이기 때문에,

 (1) BFS를 활용하면 노드들을 최단거리 순으로 기록하면서 나아갈 수 있다.

 (2) DFS를 이용하면 노드들을 최단거리 순이 아니라, 측면(왼쪽이든 오른쪽이든) 우선 순으로 단거리를 모두(트리 높이만큼 log(n)만큼) 기록한다. 애초에 DFS에서 선택하는 측면은 최단거리라는 보장이 없다. 그럼에도 노드들을 깊이 뒤적거리고, 또 뒤적거리고 하느라 시간이 오래걸린다.

3. Tip으로, visited대신 map을 그대로 사용하니 코드가 더 간결해진다.

 

최종코드:

def solution(maps):
    dir_x = [0, 1, 0, -1]
    dir_y = [1, 0, -1, 0]
    len_x, len_y = len(maps), len(maps[0])
    dqueue = deque([[0,0,1]])
    
    while dqueue:
        x, y, depth = dqueue.popleft()
        
        for i in range(4):
            nx = x + dir_x[i]
            ny = y + dir_y[i]

            if 0 <= nx < len_x and 0 <= ny < len_y:
                if maps[nx][ny] == 1 or maps[nx][ny] > depth+1:
                    maps[nx][ny] = depth+1
                    dqueue.append([nx, ny, depth+1])
                
    return -1 if maps[len_x-1][len_y-1] == 1 else maps[len_x-1][len_y-1]