프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다.

 

DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 

 

먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다.

from copy import deepcopy
import sys
sys.setrecursionlimit(100000)


def dfs(x, y, maps, cnt):
    global answer
    maps[x][y] = 0
    cnt += 1
    if x == len(maps)-1 and y == len(maps[0])-1:
        if cnt < answer:
            answer = cnt
        return
    nx = [0, 0, 1, -1]
    ny = [1, -1, 0, 0]
    for i in range(4):
        dx = x + nx[i]
        dy = y + ny[i]
        if 0 <= dx < len(maps) and 0 <= dy < len(maps[0]) and maps[dx][dy] == 1:
            map = deepcopy(maps)
            dfs(dx, dy, map, cnt)


def solution(maps):
    global answer
    answer = 10002
    dfs(0, 0, maps, 0)
    if answer == 10002:
        return -1
    else:
        return answer

먼저 DFS코드이다. 새로운 노드를 탐색할때마다 deepcopy를 이용해 행렬을 새로 할당함으로써 모든 구간의 탐색, 비교가 가능하도록 하였다. 

정확성 테스트는 모두 통과하였지만 효율성 테스트는 모두 통과하지 못했다. 예상했던 결과이고 정답을 맞추는게 목적이 아닌 DFS를 오랜만에 연습삼아 구현해보려 했기에 그러려니 했다. 최단경로 혹은 경로들을 비교하는 문제는 DFS가 아닌 DP혹은 BFS를 써야 시간복잡도에서 유리함을 여러번 경험했기 때문이다.  이 글에서 비슷한 고민을 했음을 알 수 있다.

 

따라서 다음으로 풀이를 위해 BFS로 접근하였다.

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x,y, maps, cnt):
    maps[x][y] = 0
    queue = deque([(x, y, cnt)])
    while queue:
        cash = queue.popleft()
        if cash[0] == len(maps) - 1 and cash[1] == len(maps[0]) - 1:
            return cash[2]
        for i in range(4):
            nx = cash[0] + dx[i]
            ny = cash[1] + dy[i]
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]) and maps[nx][ny] == 1:
                maps[nx][ny] = 0
                queue.append((nx, ny, cash[2] + 1))
    return -1


def solution(maps):
    answer = bfs(0,0, maps, 1)
    return answer

바로 성공한 것을 볼 수 있다. queue.append((nx, ny, cash[2] + 1))를 제외하면 BFS의 기본 구현 코드이다. 지나간 칸수를 계산하기 위해 tuple의 마지막에 count수를 세었다. deque에서 pop한 값에 1을 더하는 이유는 BFS의 탐색방법 때문이다. BFS는 수평적으로 탐색하기에 분기점이 나오면 주변을 모두 탐색하고 탐색한 값들을 다시 deque에 넣는 방식이다. 따라서 분기점 주변의 점들은 모두 분기점까지 걸린 칸 수 + 1을 해주어야 함을 알 수 있다.