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

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

프로그래머스

---

💡 문제 풀이

가벼운 BFS 문제이다.

 

최단거리를 따져야 하므로 생각할 것이 많다.

나는 이동할 수 있는 위치에 이동했을 때 최솟값을 넣어주는 방식으로 구현했다.

그리고 상대의 위치는 항상 끝에 있으므로 따로 계산안하고 넘겨주었다. 

✔️ 느낀 점

오랜만에 시작한 알고리즘이라서 파이썬 문법에 익숙하지 못하다는게 느껴졌다. 

문법에 대한 기억을 되살리는 것이 좋아보이고 새로운 것을 공부하기보단 공부한 것을 다시 되살려야겠다.

💻 코드

moves = [(1,0), (0,1), (-1,0), (0,-1)]

def solution(maps):
    row = len(maps)
    column = len(maps[0])
    
    graph = [[-1 for _ in range(column)] for _ in range(row)]
    graph[0][0] = 1
    
    queue = []
    queue.append([0, 0])
    
    while queue:
        x, y = queue.pop(0)
        
        for i in range(4):
            nx = x + moves[i][0]
            ny = y + moves[i][1]
            
            if 0 <= nx < row and 0 <= ny < column and maps[nx][ny] == 1:
                if graph[nx][ny] == -1:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append([nx, ny])
                
    return graph[-1][-1]