[프로그래머스] 파이썬 _ 게임 맵 최단거리

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

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

문제유형 : BFS

 

문제풀이 : 

• 전형적인 BFS문제로 풀면된다.
• 그래프상에서 상하좌우로 이동하면서 방문전이면서 이동가능한 위치를 큐에 삽입하면서 최단거리를 갱신한다.
  • 최단거리를 갱신할때는 count배열의 기존값과 현재값 ( 이동하기전위치값 +1 )를 비교해서 더 작은값으로 갱신
• 처음에 count배열의 초깃값을 n*m으로 설정했는데 [1,1,1] 과같은경우 3이 최솟값이 되므로 초깃값을 하나 더 크게 설정했어야했다. 그냥 앞으로는 min,max비교하기전 초기값을 웬만하면 확큰값이나 작은값으로해서 일단 맞추고보자^^..

 

정답코드 :

from collections import deque
def solution(maps):
    answer = 0
    
    
    # 무조건 오른쪽 아님 아래로만 이동한다.
    # 갈수없는곳은 0
    # 왼쪽에서 오는것 혹은 위에서 오는것 + 1
    
    # 방문처리 배열 필요
    # 4방향 모두 이동을 하는데 현재 그곳의 거리와 지금도달했을때 거리를 비교하여 최소값으로 갱신
    # 원래배열에서 0이면 무시
    m = len(maps)
    n = len(maps[0])
    
    
    global q, visited, count
    visited = [[False] * n for _ in range(m)]
    count = [[n*m+1] * n for _ in range(m)]
    count[0][0] = 1
    
    q = deque()
    q.append((0,0))
    visited[0][0] = True

    while q:
        
        curr = q.popleft()
        
        # 인접한것들중 큐에 넣을수있는것들을 넣는다.
        insert_q(curr, maps,m,n)
    
    #print(count)
    return -1 if count[m-1][n-1]== 0 or count[m-1][n-1] > n*m else count[m-1][n-1]
        

def insert_q(curr, maps, m,n):
    global visited,q, count
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    cnt =0 
    for i in range(4):
        a = curr[0]+dx[i]
        b = curr[1]+dy[i]
        if a >=0 and a<m and b>=0 and b<n:
            if maps[a][b] !=0 and not visited[a][b]:
                q.append((a,b))
                cnt += 1
                count[a][b] = min(count[a][b], count[curr[0]][curr[1]]+1)
                visited[a][b] = True