[프로그래머스] 게임 맵 최단거리 (Python)

프로그래머스 문제 풀이 - 깊이/너비 우선 탐색 (DFS/BFS)

📰 문제

문제 확인 🏃

💡 입출력 예제

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]

>> 11

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]

>> -1

💬 풀이

🎵 첫번째 풀이

from collections import deque

def solution(maps):
    row = len(maps)
    col = len(maps[0])

    dr = [0, 0, 1, -1]
    dc = [-1, 1, 0, 0]

    visited = [[False] * col for _ in range(row)]

    queue = deque()

    queue.append((0, 0, 1))
    visited[0][0] = True

    while queue:

        r, c, count = queue.popleft()

        if r == row-1 and c == col-1:
            return count

        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]

            if nr < 0 or nc < 0 or nr >= row or nc >= col or visited[nr][nc] or not maps[nr][nc]:
                continue
            
            queue.append((nr, nc, count+1))
            visited[nr][nc] = True

    return -1

✒️ 생각