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

문제

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

프로그래머스

 

 

풀이

가중치가 없는 그래프이므로 최단거리를 찾기 위해 BFS 알고리즘을 사용한다

그래프의 최대 크기가 100x100이므로 인접행렬을 통해 그래프를 만든다

 

 

코드

python

def bfs(row, col, maps):
    q = [[row, col]]
    
    dist = [[-1] * len(maps[0]) for _ in range(len(maps))]
    dist[row][col] = 1
    
    while q: 
        cur = q.pop(0)
        for d in range(4):
            dx = [0, 0, 1, -1]
            dy = [1, -1, 0, 0]
            next_row = cur[0] + dy[d]
            next_col = cur[1] + dx[d]
            
            if next_row < 0 or next_row >= len(maps) or next_col < 0 or next_col >= len(maps[0]):
                continue
            
            if dist[next_row][next_col] == -1 and maps[next_row][next_col] == 1:
                q.append([next_row, next_col])
                dist[next_row][next_col] = dist[cur[0]][cur[1]] + 1
    
    return dist
    
 
def solution(maps):
    answer = bfs(0, 0, maps)
    return answer[len(maps) - 1][len(maps[0]) - 1]