[프로그래머스] [Python] 게임 맵 최단거리 - bfs, dfs

dfs로 풀면 시간초과가 뜬다.

이번 게임 맵 최단거리 문제 풀이의 알고리즘에서 가장 키포인트는 최단 거리 구하는 알고리즘을 선택하는 것입니다. 최단거리 구하기는 모든 지역을 깊이 있게 훑어봐야하는 깊이 우선 탐색(DFS)보다 현재 위치에서부터 가까운 위치를 탐색하면서 넓게 거리를 탐색하는 너비 우선 탐색(BFS) 알고리즘을 선택하는 것이 바람직합니다.

#dfs 풀이 -> 시간초과 뜸

n= 0
m = 0
ans = -1
xs = [0, 1, 0, -1] # right, up, left, down 
ys = [1, 0, -1, 0]
map = []

def solution(maps):
    global n,m
    global map
    map = maps
    n = len(maps)
    m = len(maps[0])
    visited = [[0 for j in range(m)] for i in range(n)]
    visited[0][0] = 1
    dfs(0,0,0, visited)
    if ans == -1:
        return ans
    else:
        return ans+1

def dfs(x, y, cnt, visited):
    global ans
    
    if x == n-1 and y == m-1:
        if ans == -1:
            ans = cnt
        elif cnt <= ans:
            ans = cnt
        return
    if x < 0 or y < 0 or x >= n or y >= m:
        return
    for i in range(0, 4):
        tx = x + xs[i]
        ty = y + ys[i]
        if tx >= 0 and ty >= 0 and tx < n and ty < m:
            if visited[tx][ty] == 0 and map[tx][ty] == 1:
                visited[tx][ty] = 1
                dfs(tx, ty, cnt+1, visited)
                visited[tx][ty] = 0

 

 

#bfs 풀이
from collections import deque
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
n = 0
m = 0
def solution(maps):
    answer = 0
    global n,m
    n = len(maps)
    m = len(maps[0])
    answer = bfs(maps, 0, 0)
    if answer == 1:
        return -1
    else: 
        return answer

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