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

🔗 링크

게임 맵 최단거리

설명

• 해당 문제의 답을 구하는 것을 bfs 와 dfs 둘 다 사용할 수 있음

❌ DFS (타임오버)

깊이 우선 탐색

# 깊이 우선 탐색

def solution(maps):
    if len(maps) == 1 and len(maps[0]) == 1:
        return 1
    row_len = len(maps)
    vec_len = len(maps[0])
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    # 맵 받기
    def dfs(row, vec, count):
        if maps[row_len - 1][vec_len - 1] != 1 and count >= maps[row_len - 1][vec_len - 1]:
            return
        maps[row][vec] = count
        for x, y in zip(dy, dx):
            new_row = row + y
            new_vec = vec + x
            if new_row < 0 or new_row >= row_len or \
                new_vec < 0 or new_vec >= vec_len or \
                maps[new_row][new_vec] == 0 or \
                (maps[new_row][new_vec] != 1 and 
                 maps[new_row][new_vec] <= count + 1):
                continue
            dfs(new_row, new_vec, count + 1)

    dfs(0, 0, 1)
    goal = maps[row_len - 1][vec_len - 1]
    return goal if goal != 1 else -1

• 깊이 우선 탐색으로 풀면 위와 같은데 효율성 테스트에서 문제가 발생

타임 오버 이유

• 재귀 함수를 호출하여 스텍을 사용하는 dfs의 구조상 모든 경로를 다 탐색해봐야함. 따라서, 큐를 사용하는 너비우선 탐색에 비하여 시간이 오래 걸림

✅ BFS

너비 우선 탐색

# 너비 우선 탐색
from collections import deque

def solution(maps):
    if len(maps) == 1 and len(maps[0]) == 1:
        return 1
    row_len = len(maps)
    vec_len = len(maps[0])
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    # 맵 받기
    def bfs():
        queue = deque()
        queue.append((0, 0))
        
        while queue:
            row, vec = queue.popleft()
            if (row, vec) == (row_len - 1, vec_len - 1):
                return maps[row][vec]
            for (y, x) in zip(dy, dx):
                new_row = row + y
                new_vec = vec + x
                if new_row < 0 or new_row >= row_len or \
                    new_vec < 0 or new_vec >= vec_len or \
                    maps[new_row][new_vec] == 0 or \
                    (maps[new_row][new_vec] != 1 and 
                     maps[new_row][new_vec] <= maps[row][vec] + 1):
                    continue
                maps[new_row][new_vec] = maps[row][vec] + 1
                queue.append((new_row, new_vec))
        return -1

    return bfs()

• 다음과 같이 deque (그냥 queue를 사용해도 무방) 를 사용하여 효율성 테스트 통과