🎀 본 게시물은 프로그래머스 연습문제 풀이 게시물입니다. 🎀

---

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

미로 최단거리 문제는 BFS로 푼다.

nxn이 아니라 nxm으로 행과 열이 다른 격자판인것을 인지하자

---

🚀 나의 풀이 ⭕

from collections import deque

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def solution(maps):

    n = len(maps)       # n행
    m = len(maps[0])    # m열

    graph = [[-1]*m for _ in range(n)]
    graph[0][0] = 1

    queue = deque()
    queue.append([0, 0])

    while queue:
        y, x = queue.popleft()

        # 현재 위치에서 4가지 방향으로 위치 확인
        for i in range(4):
            nx = x + dx[i]      # 열 이동: 좌,우
            ny = y + dy[i]      # 행 이동: 상,하
            
            if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1:
                if graph[ny][nx] == -1:                 # y,x순이어도 헷갈리지말자
                    graph[ny][nx] = graph[y][x] + 1
                    queue.append([ny, nx])

    return graph[-1][-1]        # 도달했으면 -1에서 거리 값으로 변했을것이고 아니면 그대로 -1을 출력할 것이다.
    

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기