Programmers / 2단계 / 깊이/너비 우선 탐색(DFS/BFS) / python /

코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr)

 

나의 풀이 

.

 

 

 

모범 답안

from collections import deque
def solution(maps):
    n = len(maps); m = len(maps[0])
    visited = [[False] * m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[0][0]=True
    while q:
        y, x = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n and maps[ny][nx] == 1: # 맵을 벗어나지 않고 벽이 아니라면
                if not visited[ny][nx]: # 방문하지 않았다면
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    maps[ny][nx] = maps[y][x]+1
    if maps[n-1][m-1]==1:
        return -1
    else:
        return maps[n-1][m-1]

 

 

알게된 점

재귀 함수를 호출하여 스택을 사용하는 DFS의 구조상 모든 경로를 다 탐색해봐야 한다.

따라서, 큐를 사용하는 BFS에 비하여 시간이 오래 걸리기 때문에 최단 경로를 탐색할 때에는 BFS를 사용하는 것이 효율적이다.