[Python] 프로그래머스 Lv.02 - 게임 맵 최단거리

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

[ 알고리즘 ]

BFS/DFS

 

[문제 접근]

BFS 최단거리 구하는 전형적인 문제이다. 최단거리를 찾기 위해 1을 찾을 때 마다 그 전의 값에 +1 을 해주고,

만약 모든 과정이 끝났는데 (=큐가 비었는데) (n,m)의 값이 아직 1이라면 벽에 막혀 지나가지 못하는 자리임을 알 수 있음

 

[코드]

from collections import deque
def solution(maps):
    answer = 0
    que=deque()
    
    n=len(maps[0]) # 가로
    m=len(maps) # 세로
    
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    
    que.append((0,0)) # (0,0)에서 출발
    
    while que:
        x,y=que.popleft()
        
        for i in range(4):
            xx=dx[i]
            yy=dy[i]
            
            if x+xx <0 or y+yy<0 or x+xx >=m or y+yy>=n:
                continue
                
            if maps[x+xx][y+yy]==1:
                que.append((x+xx,y+yy))
                maps[x+xx][y+yy]=maps[x][y]+1
                
    if maps[m-1][n-1]==1:
        answer=-1
    else:
        answer=maps[m-1][n-1]
                    
    return answer