그래프(BFS) - 게임 맵 최단거리

1.문제

2.소스

from collections import deque

def solution(maps):
    yLen = len(maps)
    xLen = len(maps[0])
    goalY, goalX = yLen - 1, xLen - 1
    dy = [0, 0, 1, -1]
    dx = [-1, 1, 0, 0]
    
    queue = deque([(0,0,1)])
    while queue:
        curY, curX, move = queue.popleft()
        if curX == goalX and curY == goalY:
            return move
        for i in range(4):
            y = curY + dy[i]
            x = curX + dx[i]
            if y >= 0 and y < yLen and x >= 0 and x < xLen and maps[y][x] == 1:
                queue.append((y, x, move + 1))
                maps[y][x] = 0
    return -1

3.문제분석
bfs로 최단거리를 찾는 문제다

해결방법
1)
지도의 가로, 세로길이, 시작좌표, 도착좌표를 전역변수로 만들고
상하좌우좌표를 통해 이동하면 된다

2)
조건은 이동한 x,y좌표가 0보다 크고 x좌표가 열보다 작고 y좌표가 행보다 작고
배열에서 이동할 수 있는곳으로 표시된 1인지 확인한다

3)
좌표와 이동횟수를 입력하고 이미 이동한곳을 배열에 표시한뒤
목표좌표에 도달했는지 확인하고 도달했으면 이동횟수를 리턴한다

4)
모든 이동가능한 좌표를 탐색한뒤
queue가 비었으면 while문이 끝나고 -1을 리턴한다

4.하고싶은말