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

문제 링크

풀이

from collections import deque
def solution(maps):
    n = len(maps) # 행
    m = len(maps[0]) # 열
    visited = [[False] * m for _ in range(n)]
    directions = [[0,1],[0,-1],[1,0],[-1,0]]
    queue = deque([(0,0,1)])
    visited[0][0] = True
    while queue:
        x, y, dis = queue.popleft()
        if x == n - 1 and y == m -1:
            return dis
        for dx, dy in directions: 
            nx = x + dx 
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx,ny, dis + 1))
                
    return -1     

풀이 해석

• directions를 통해 동서남북 방향전환을 표현함
• BFS를 이용하여 풀이 queue의 사용
• while queue를 통해 queue가 빌때까지 반복하고 x = n-1, y = m-1이 될때 distance값을 출력하게 하였다
• for 문에서 방향전환을 더해가며 maps값이 1이고 방문하지않은 조건을 모두 만족해야 방문하게 조건문을 설정하였다
• 그 뒤 조건이 성립하면 True로 바꿔주고 distance값을 1늘려 append해준다