프로그래머스 - 게임 맵 최단거리

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

프로그래머스

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    v = [[0]*m for _ in range(n)]
    
    
    move= [[-1,0],[1,0],[0,1],[0,-1]]
    
    def bfs():
        q = deque()
        q.append([0,0,1])
        
        while q:
            x,y,depth = q.popleft()    
            
            #4방향을 고려
            for i in range(4):
                dx = x + move[i][0]
                dy = y + move[i][1]
                
                # 그래프 범위 확인
                if n>dx>=0 and m>dy>=0:
                	#벽이 아니고 방문기록이 없을 때
                    if maps[dx][dy]!=0 and v[dx][dy]==0:
                    	#방문처리 후 depth+1증가
                        v[dx][dy]=1
                        maps[dx][dy] = maps[x][y] +1
                        q.append([dx,dy,depth+1])
                        
        return maps[n-1][m-1]
                        
    answer = bfs()
      
    if answer ==1:
        answer = -1
    
    return answer

bfs를 사용한 풀이

 

dfs는 100x100 그래프 형식일 때 시간 효율이 떨어짐

 

따라서 최소거리를 구하기 위해서는 bfs를 이용하여

원하는 좌표까지의 깊이를 구해주는 것이 중요!