[Python - 프로그래머스] 게임 맵 최단거리(DFS/BFS 연습)

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

프로그래머스

 

---

Solution

 

from collections import deque
def solution(maps):
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    
    r = len(maps); c = len(maps[0])

    visited = [[False]*c for _ in range(r)]

    que = deque([(0,0)])
    while que :
        x,y = que.popleft()
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]

            if nx <0 or nx >=r or ny < 0 or ny >= c :
                continue

            if visited[nx][ny] == False and maps[nx][ny] == 1:
                visited[nx][ny] = True
                maps[nx][ny] = maps[x][y] + 1
                que.append((nx,ny))

    ans = maps[r-1][c-1]
    return  ans if ans != 1 else -1

 

최단거리는 보통 BFS로 푼다.

 

dx, dy, for(4)로 사방으로 진행하는 것이 포인트이다.

단, 각 방향으로 진행 가능한지 확인하는데, 이는 visited 라는 새 list를 만들어 관리한다.